It seems to be one of those canons of historical folklore that when medieval cartographers were drawing up sea charts and they got to the limits of what was known, they drew pictures of fanciful sea beasties at the edges and dutifully noted “Here be dragons”. This just seems too cute to be true, though: does it have any basis in fact, or was it a later “look how ignorant and fearful our ancestors were” invention? I’ve seen old charts with various fanciful denizens of the deep drawn on them - improbable looking dolphins and the like - but they seem more like artistic licence to fill in the boring blank bits of sea than any serious warning to mariners.
Apparently not. The closest anyone came to it was on the Lenox Globe and even then, they may not have been talking about smoky reptiles.
Cool. Very cool. Many thanks: stuff like this is why I pay to come here. I guess the next, harder to answer question, is when the phrase entered historical folklore.
You might also try this guy named Cecil who writes for the Chicago Reader. He sometimes answers questions like this.
Alas, that Cecil guy is less than thorough sometimes: one might even call that column woefully slapdash. Further research {OK, half an hour on Google} reveals that the phrase appears to have entered the popular lexicon some time between 1879 when the text of the Lenox Globe was published, and 1928 when a similar reference appeared in a Dorothy Sayers story.
While I don’t think your characterization of Cecil is correct, I thank you for the interesting link.