The Mongols invaded southern China. Mind you, that's NOT horse country. It's very mountainous, humid, and covered in rivers and rice paddies. Furthermore, the Song had large and well-armed professional armies and advanced technology, large portions of their troops being armed with crossbows, and which were experienced in fighting cavalry armies. Their navy controlled the rivers and could prevent crossings as well as resupply, deploy, and evacuate troops.
The city of Xiangyang was a strong fortess with five-foot-thick walls, and was close to the fortress of Fancheng. The two fortresses could resupply and defend one another by means of the river. Each had enough supplies to last years, and again, they could get resupplied anyway. Each had large garrisons of infantry. The Mongols besieged them, but they held out. The siege dragged on for five years until the Mongols acquired counterweight trebuchets. They then pounded Fancheng into submission and got the governor of Xiangyang to surrender by promising him control of Fancheng as well.
I don't know if the HRE would be as formidable as you think. It was a pretty loose confederation of princes, bishops, and counts who were at each other's throats as often as by their side. Besides, when the Mongols launched a punitive invasion of Hungary (and Poland), it ended poorly for the Europeans. And, of course, most Russian states fell quickly to the Mongols.
If decades of warfare and a five-year siege of strongholds in hostile terrain against a numerous, powerful, well-equipped, and well-supplied enemy couldn't stop them, and if Europeans had fallen to Mongols before, I'm not sure if Europe would have stopped them had the Mongols hit it as hard as they hit Khwarezm or the Song.
