Is the story that Europe believed that the Mongols were a Eastern Christian Kingdom led by 'Prester John' on a mission to destroy Islam based in a lot of fact or is it another example of bad history.

This was indeed a belief present during this time. They believed the Mongols to be lead by a virtuous Christian monarch named "King David" (possibly a very distorted corruption of the name "Chingghis). There was even an embellished account of the victories of this great Christian ruler, called the "Relatio de Davide rege Tartarorum Christiano".

The context for the spread of these rumors was the Fifth Crusade, the last of the crusades to the Holy Land to have been organized by the Pope (subsequent 'crusades' to the region were carried out on the personal initiative of kings and not as a response to a papal call to arms). Things didnt go to well for the crusaders but at some point they began to hear reports that powerful Muslim kingdoms were being sacked by some nation located even further to the East. And that not only were the powerful Something that couldve caused the confusion was that Christianity was actually present amongst the Mongols, Genghis Khan had Christian generals and later on the mother of Kublai Khan was a Christian. While the Mongols followed what is nowadays called the "Tengri" religion, they did have amongst their numbers many Christians as well as Muslims, Buddhists and other faiths. The constant religious wars that Western Europeans have gotten used to might've made it such that they couldnt really grasp the idea of there being a large nation that only freely tolerated numerous religions without much discrimination. So when they heard that the Mongols were burning Muslim cities and had Christians in their ranks, they seemed to have then thought that the Mongols were a wholly Christian nation engaged in something that could be seen as a "westward" heading crusade.

Anyway, here's a quote from HW Hazard's account of this rather interesting episode-

After the fall of Damietta in November 1219, James of Vitry "preached publicly that David, king of the two Indies, hastened to the help of the Christians, bringing with him most ferocious peoples who will devour like beasts the sacrilegious Saracens."9 James of Vitry's information was based on a report originally written in Arabic and then translated into French and finally into Latin, a Relatio de Davide rege Tartarorum Christiano. The terrible distortion of proper names notwith standing—they are often unrecognizable—the Relatio contains a summary but not altogether inaccurate report of the Mongol campaigns between 1218 and 1221. In it the deeds of Chinggis (Genghis Khan) are attributed to a king David, "who is usually called Prester John," a somewhat unexpected identification if we consider that the latter was thought of as an adult some eighty years earlier. The Mongol conquest—known to Europe largely through James of Vitry and the legate Pelagius—raised considerable hopes, and in 1221 in an encyclical letter Honorius III announced in glowing terms to the archbishops of Gaul and to the English clergy that king David, commonly called Prester John, a God-fearing man, offered battle to the shah (called soldano Persidis) of Persia, occupied his land, and was only ten days' journey from Baghdad.11 It is perhaps not too far-fetched to suggest that these rumors, widely circulated since 1219, were a decisive factor in Pelagius's rejection of the extremely favorable peace offer made by al-Kãmil.12 In 1221 the identification of king David with Prester John and of his people with the Mongols was generally accepted. The fact that in the winter of 1220—1221 the Mongols attacked Georgia was conveniently ignored by Pelagius, who urged the king of Georgia, George Lashen IV, to send a contingent to Damietta.