I was listening to Dan Carlin's Hardcore History and he seemed to imply that after a long game of "medieval telephone" Genghis Khan's name turned into "Prester John." He certainly was someone who attacked Muslims in the East, and they do sound very similar, but did they sound similar in the tongues back then? Was Genghis really Prester and they had to pretend he wasn't once they found he wasn't Christian?
Also, is Dan Carlin a good source? The podcasts are very well done and interesting so far but I've only hear 6 or so.
I've listened to the whole Wrath of the Khans series of podcasts several times and can say with some degree of certainty that Dan Carlin never makes the claim that the name of Prester John is derived from Genghis Khan. The stories of the mythical figure predate the birth of the historical one, or at least any time when the name could've possibly spread all the way to Europe. It's just that when rumours of the Mongol conquests of the Islamic world started spreading West, a lot of people connected them to this particular legend.
I know Wikipedia isn't held in very high regard on this subreddit, but the article on Prester John is a pretty good one.
There's a whole section in the FAQ about Dan Carlin that you might want to check.
As far as if Dan is a good source or not, here is a discussion we had in this sub from about a year ago. http://www.reddit.com/r/AskHistorians/comments/12i31q/dan_carlin_history_or_bunk/ basically it boils down to he is entertaining and hits a lot of the points but isn't the be all end all by any stretch.
I listened to the whole series, and here's what I got out of it, regarding the "Prestor John" subject:
The Prestor John myth regarded a supposed Christian kingdom lying somewhere in the East
Nestorian Christian missionaries had succeeded in converting substantial groups of Turkic peoples somewhere in Western Asia (I can't recall the name of the peoples mentioned, but I do remember that the Mongols eventually conquered / assimilated them)
The Muslim World -- which Christendom was currently at war with -- was suddenly besieged by some power from the East
Thus, the Christians jumped to the conclusion that this mysterious invading force was the much-rumored Prestor John.
But, as mentioned by others, the legend predates Genghis Khan; the Mongols were simply one of a number of identifications the Christians associated the legend with -- India, Ethiopia and North America would all be others.
I have heard lots of theories on the origin of the legend..my favorite is that it was a memory of the Byzantines in Constantinople by those left in the West after the Fall of the Roman Empire in the west.
The Legend of Prester John is much older than Genghis Khan himself. In fact, the hoax letter was presumably written around 1165, which was around the time Genghis was born. It's possible the Prester John later become associated with Ghengis in some way, but there is no way he is the origin of the legend itself.