These losses are exceptions that prove the point. After conquering all of China the Mongols then had enough military and political power to waste armies of thousands in pointless wars on the periphery of their empire.
The Egyptian Mamluks victory over the Mongols was while Hulegu Khan and the main force had returned to Mongolia to elect a new Great Khan. The man Hulegu left in charge decided to keep expanding with his much reduced forces, and this is the army that the Mamlukes defeated.
That is certainly true, but surely Europe is at the periphery of their empire?
The Mamluks also did more than just win one single battle. While you can argue with reasonable accuracy that it was internal squabbling amongst the Mongols which prevented them being crushed, the Mamluks won a string of victories between 1260 and 1300~. This is interesting, because the Mamluks have quite a few things in common with your traditional European cavalryman of the period.
The current Holy Roman Emperor, Frederick II, was involved in a battle with the Pope for supremacy. The Pope was the Vicar of Christ in a time when people really believed that. That this conflict existed points to the universality of the Imperial title. The conflict was between the two positions (and men who occupied them) which could justly lay claim to mantle of leadership for all Christiandom.
Universal on paper but not in practice. You seem to be drawing the conclusion that the conflict implies both are equally strong, my interpretation is infact that both are equally weak. Neither side really defeated the other, both found it relatively easy to continue the conflict. Frederick effectively gained support for his Italian war by sacrificing the very authority I talked about. He granted greater independence for German princes which causes the HRE's power to weaken from then onwards. Even then there is a major difference between the "HRE" as it stood and a European Khanate stretching from the Volga to the Atlantic. In a similar vein the Pope could inspire people to go on Crusade but lacked the ability to force people to go. The Church may have been universal but its actual authority in temporal matters was limited.
The Mongols are going to ride their horses across Europe, burn down unwalled towns and villages and kill as many peasants as they can get their hands on. They don't need supply lines. They'll attack during the harvest, living off the land, and the land will at least support a single season of campaigning. The Mongols don't need to take castles or cities. They can drive the peasants into the strong places and then burn down everything outside of them. The strong places don't produce food, and can't feed the swelled population. Disease, starvation, cowardice, the strong places fall. Happens faster with their Europeans allies siege trains.
The Mongols' goal is simple. They're going to kill lots of peasants and destroy some armies. They were capable of very sophisticated diplomacy and I think that this show of force is going to bring in the European allies that they need.
So the Mongols just roam at will, presumerably in fairly significant numbers, otherwise they will be killed by simple attrition, meanwhile avoiding any and all fortifications worthy of the name? Living off the land is fine for people, it isn't so fine for horses. If the Mongols are reduced to a central European (Germany/Italy) ratio of horses (maybe one per person at best) they will not be faster than their European foes. If they are not faster than their European foes, they can be brought to battle. At this point they will find themselves forced to fight, possibly on foot, against far larger armies and they will probably be cut down. Why do you imagine the Europeans will endlessly behave in the same way, launching impetuous charges which go awry and leading to a subsequent massacre? The Mongols are not invincible. Their primary advantage over their European foes is their greater command of in-battle strategy. Yet if you remove the horses, their options are greatly diminished. A feigned flight doesn't work so well if you cannot actually escape.
If the Mongols are taking castles and cities with European (or Chinese) siege trains then once again the question of supply lines comes into play. You have to feed the people and horses who are going to besiege these fortifications, possibly for months. This is going to be difficult if the peasant population has been decimated.
Also in regards to universal positions, you can't have it both ways. The Mongols are unlikely to be in favour of the authority of either the Emperor or Pope. These two are likely to oppose them strongly. That the Mongols can find European allies against these two (only France really comes to mind, possibly Venice at a push) rather indicates their lack of universal authority. Personally I think the ability to play divide and rule would diminish as the nature of the Mongol threat was realised. A force which has ravaged Hungary is one thing. One which has routed the Holy Roman Emperor and had the Pope crushed in a carpet is quite another.
I'm not claiming that all the nobles will suddenly lay down their arms. What I am saying is the Mongols will be in a position to offer some of the European nobility the ability to vastly improve their position within the pre-existing hierarchy. The feudal structure would work well for the Mongols, because they would be able to kill a relatively few number of people in order to inherit the power structure.
Also, the moment that they are choosing to attack is really a big part of the success of their campaign. Their is no Pope, thus no one to declare a Crusade against them, and I think that France's King would really be willing to martyr himself.
The theory being that the Mongols can just kill a few people and then set themselves up as the top of the Feudal food chain. Except that this theory implies that those below them are loyal to the system. They are not. The only reason people are going to pay tribute is if the Mongols establish something which can enforce their will, i.e an occupationary force of some description. Occupying all of Europe will take far longer than a year or two.
What independence will the Mongols grant exactly? The very imposition of levied tribute, rather than military service, is something many nobles are not entirely used to and will probably resent.
Where are you getting this idea that there is no Pope from? You may be right in the very specific short term (1242?), but Innocent IV is there by the middle of 1243. There seems to be no reason why a Mongol invasion would prevent the election of a Pope.
The Muslim Mamlukes, as noted, were at the defeated a depleted force operating at the periphery of the empire. The Europeans are facing a Mongol group that has decided that Europe is their golden ticket.
They defeated a depleted force in 1260 and then went on to win several battles through the rest of the century. When the Mongols ignored basic military strategy (such as riding around Western Europe with contempt for supply lines) they paid the price. The Mamluk force may have outnumbered the Mongol force, but such a situation is likely to be repeated in Europe.
There is a difference between a carefully planned, step by step invasion over the course of decades (something which is unlikely to happen given Mongol politics) and a smash and grab raid over the course of a year or two which somehow not only brings Europe to her knees (apparently most of these battles are bloodless for the Mongols) but manages to unite her; something no one has managed for half a millenium.
Mongol terror wasn't common. Read the history of their conquests. Mountains of skulls, the skinning of entire cities. Depopulation that takes generations to come back. Europeans didn't do war like the Mongol did. No one did. That's why they won like no one ever did.
Mongol terror may not have been common, but it doesn't matter. The nobility have been bred not to fear death and chivalrous conflict, especially with the pagan or heretic, is to be commended. Obviously some people embrace this idea more than others. If anything Mongol terror may well prove to be counter productive inspiring a growth in religious fervour and a view that the end is most definately nigh. In my view comparing feudalistic Europe to the civilised and centralised Muslim and Chinese Empires isn't sensible.
If Hungary faced what can be expected of a Mongol invasion, her situation is notable. Yes her peasant population were cut down, possibly as many as half being slain. Yes large numbers of immigrants would be brought in to make up for the dead. Despite this Hungary was still capable of playing the Feudal war of the period, fighting Austria and Bohemia. If the peasants had been culled, the feudal lords who are key to the European system emerged from their forts and could and did continue to wage war.
- it could also have a big impact on Russia and the western steppes. The Mongol conqueror's of Europe would come from what became in OTL the Golden Horde and the two would be linked for a while at least. An early conversion might well mean that TTL's GH equivalent also goes Christian, although whether Catholic or Orthodox would be an interesting point.