Geoffrey of Monmouth on the Dates of Arthur
The 12th century cleric Geoffrey of Monmouth provides us with our earliest information on Merlin. Geoffrey of Monmouth wrote about the early history of Britain in Historia regum Britanniae (the "History of the Kings of Britain") and Vita Merlini ("Merlin's Life"), which was adapted from Celtic mythology. Being mythology-based, Merlin's Life is not enough to say Merlin ever lived. To determine when Merlin may have lived, one way would be to date King Arthur, the legendary king with whom Merlin is associated.
Geoffrey Ashe, an historian and co-founder and secretary of the Camelot Research Committee, wrote about Geoffrey of Monmouth and the Arthurian legend. Ashe says Geoffrey of Monmouth connects Arthur with the tail end of the Roman Empire, in the late 5th century A.D.:
"Arthur went over to Gaul, the country now called France, which was still in the grip of the Western Roman Empire, if rather shakily."
"This is one of the clues, of course, to when Geoffrey [of Monmouth] thinks all this is happening, because the Western Roman Empire ended in 476, so, presumably, he's somewhere in the 5th Century. Arthur conquered the Romans, or defeated them at least, and took over a goodly part of Gaul...."
- from (www.britannia.com/history/arthur2.html) Basic Arthur, by Geoffrey Ashe
The 1st Use of the Name Artorius (Arthur)
The name of King Arthur in Latin is Artorius. The following is a further attempt to date and identify King Arthur that places Arthur earlier in time than the end of the Roman Empire, and suggests the name Arthur may have been used as an honorary title rather than a personal name.
"184 - Lucius Artorius Castus, commander of a detachment of Sarmatian conscripts stationed in Britain, led his troops to Gaul to quell a rebellion. This is the first appearance of the name, Artorius, in history and some believe that this Roman military man is the original, or basis, for the Arthurian legend. The theory says that Castus' exploits in Gaul, at the head of a contingent of mounted troops, are the basis for later, similar traditions about King Arthur, and, further, that the name Artorius became a title, or honorific, which was ascribed to a famous warrior in the fifth century."
- from (/www.britannia.com/history/timearth.html) Britannia's Timeline
Does King Arthur Belong to the Middle Ages?
Certainly the legend of King Arthur's court started in the Middle Ages and the Medieval History Guide has a fine collection of links on the subject, but the putative figures on which the legends are based, appear to come from before the Fall of Rome.
In the shadows between Classical Antiquity and the Dark Ages lived prophets and warlords, druids and Christians, Roman Christians and the outlawed Pelagians, in an area sometimes referred to as Sub-Roman Britain, a pejorative label suggesting that the native British elements were less advanced than their Roman counterparts.
It was a time of civil war and plague -- which helps explain the lack of contemporary information. Geoffrey Ashe says:
"In dark age Britain we have to recognize various adverse factor, such as the loss and destruction of manuscripts by invading armies; the character of the early material, oral rather than written; the decline of learning and even literacy among the Welsh monks who might have kept reliable records. The whole period is plunged in obscurity from the same causes. People who were certainly real and important are no better attested."
Since we don't have the necessary fifth and sixth century records, it's impossible to say absolutely that Merlin did or did not exist.
- From Tennyson's "Idylls"
The pale blood of the wizard at her touch
Took gayer colours, like an opal warmed.
She blamed herself for telling hearsay tales:
She shook from fear, and for her fault she wept 
Of petulancy; she called him lord and liege,
Her seer, her bard, her silver star of eve,
Her God, her Merlin, the one passionate love
Of her whole life; and ever overhead
Bellowed the tempest, and the rotten branch 
Snapt in the rushing of the river-rain
Above them; and in change of glare and gloom
Her eyes and neck glittering went and came;
Till now the storm, its burst of passion spent,
Moaning and calling out of other lands, 
Had left the ravaged woodland yet once more
To peace; and what should not have been had been,
For Merlin, overtalked and overworn,
Had yielded, told her all the charm, and slept.