Prester John is best understood as a mythological figure whose stories were influenced by real figures (analogies might be Robin Hood or King Arthur), rather than being a mythologised historical figure (such as Charlemagne).

Prester John quite obviously isn't directly related to Genghis Khan, as some of the earliest written mentions come from Chronica de duabus civitatibus by Otto of Freising which was written 1143–1145, before Genghis Khan was born, and the Letter of Prester John which dates from 1165 when Genghis was 2 or 3 years old.

As far as the influence of Genghis Khan on the legend is concerned, Michael E. Brookes' thesis covers it well:

The westward expansion of the nomadic Mongols did not go unnoticed in Europe, and the history of Mongol drive across Asia need not be recounted here. However, two particular Mongol leaders, Genghis Khan and Hulagu Khan, stand out as figures that may have played roles in the evolution of the Prester John legend. Europeans retained memory of the Nestorian Christian churches in Asia, and there were a significant number of Nestorians who held important positions in the Mongol government. Moreover, Europeans knew from experience the powerful armies that surged westward across the steppe, and the conquest of Baghdad by Hulagu Khan likely cemented the idea that an eastern ally could open a deadly flank upon the Islamic world.

Brookes' thesis is just generally a good read for analysis of the Prester John myth. I'd also recommend Kurt - The search for Prester John,a projected crusade and the eroding prestige of Ethiopian kings,c.1200–c.1540 for more detail on the later, Ethiopian influences.

There is some kind of connection, but it is not in the names.

The first mentions can be dated in the mid-12th century. The Prestor or Presbyter John is named in a letter from a byzantian bishop to pope Eugene III in which the bishop requests help in the fight against the muslims and casually drops the existence of a mighty christian ruler in the far east. This letter was picked up by german chronicler and bishop Otto von Freising who eternalised John in his Chronica sive Historia de duabus civitatibus. (This is also featured in Umberto Ecos Baudolino - reading is recommended).

The idea of this mighty christian ruler comes to Europe in a time of struggle against the muslims. Edessa was just lost and the 2nd crusade was about to start. Now enter Genghis Khan. When the europeans first heard tales about his deeds, some of them believed that he must be Prester John. Who else could stir up Asia if not the mystic christian ruler? However, europeans quickly came to realise that this guy probably wasn't your prototype christian, quite the contrary. Now some people believed the mongols to be the apocalyptic people of Gog and Magog.

Soon after the first impact on Europe however, the pope send a delegation to the mongols and tried to establish dimplomatic relations. There was hope that the mongols might be converted to Christendom and be allies in the fight against the muslims. Keep in mind that this was the original idea of the Prester John in the 12th century. In the end they converted to Islam though.

But even after the age of crusades in the levante, i.e. 1291, the fascination Prester John didn't cease to exist. In the 14th century there was a rise in journey literature. Travel report like the ones of Marco Polo or the fake John Mandeville included the tales about Prester John and his glorious kingdom which today read like heaven on earth. They took the descriptions from older literature and even antic and early medieval encyclopedias like the one of Isidor of Sevilla.

So, while the names of both aren't really related, Prestor John and Genghis Khan share some common history, at least from a european perspective. I can recommend you some further reading tips. However I'm not at home now, so it can take a day until I can do this. Hope I could be of help.