Mongolian horses were, as I recall, smaller than the European horses. In addition, they're probably more surefooted than battlehorses, and the Europeans or whoever else they fought would NOT be prepared for the Mongols' REMOUNTS. Horses tire slow, but don't recover fast at all, so a man marching versus somebody solely using a horse are going to reach a distant destination at about the same time. If, however, you can just keep swapping horses and don't care about making one lame as a result of injury going through difficult terrain...
Yeah. The Mongols' approach to warfare was terrifyingly effective...against the masses of peasant levies common in armies of the time. They'd've fared MUCH poorer against late-medieval mercenary companies in munition plate (three-quarters plate, doesn't protect the legs to save weight and money). And, of course, you run into the ultimate problem of medieval Europe:
20000 castles. In France. Just in France. That's 20,000 sets of walls you must batter down or build siege towers to get across. While you do so, 19,999 armored men on horses (The knights or lords of the castles you AREN'T presently besieging...) with their retinues (some of whom will be armored knights in their own right) and levies are making your life one continuous, slowly starving hell, because they don't want you in their country either.
And that fun is just if you reach France. First you've got to get past the Holy Roman Empire, which is neither Holy, nor Roman, but that's neither here, nor there. The HRE has plenty of castles all its own. Which means that if you reach France, your army is worn down, you have no supply lines (you can't hold all those castles without running out of army), and, again, everyone in the area hates you and wants you dead, and they've had several thousand years of practice at killing people, because Europe is just such a lovely place like that, after all.
By the way, the Mongols never successfully made it past Russia. They might've lost to the Russians, too, had the Russian princes not dissolved and headed home after the Mongols faked a retreat.