While the Mongol conquests were, in my opinion, in aggregate the most succesful military action in human history, the were not strictly speaking unprecedented. There had been a long series of steppe empires that preceded them, all presenting roughly similar threats to the agrarian states at the Eurasian border (skilled horsemanship, and incredible capacity to mobilize populations for war, and a social structure that promoted capable military leaders being a few of the traits that gave them success). The steppe armies, being rather similar in the makeup over the couple thousand odd years of their military dominance, often used similar tactics, relying on their mobility to chip away at their opponent with bows and arrows before moving in for the kill after the enemy's cohesion was broken. This was very difficult to cope with, and indeed the most succesful and widely practice method of defeating steppe armies was hiring other steppe armies, but it was not impossible. In the second century the Alans, an Iranian people who had often presented headaches for the Parthians, began intruding on Rome's eastern provinces. In one assault, they were met by Arrian, the governor of Cappadocia (in southeastern Turkey), who managed to fight them off and then included a substantial section on this in his work on military tactics.

The full section is here. I apologize for the rather unscholarly seeming site, due to the somewhat perverse incentives of classics there is a new translation of Homer or Eurypides every year but there ha snot, to my knowledge, been a full translation of the Tactica. Anyway.

It isn't super long and the most relevant bit is in the last two paragraphs, so it is worth at least reading them. But what you will note is that the plan Arrian describes is based entirely on the disciple and organization of his armies. It requires that he is able to effectively subdivide his forces (notably his cavalry into a pursuit contingent and a support contingent), and for his infantry to be able to unflinchingly stand up to the steppe tactics they face. History proves again and again that this is far from easy, and armies with the capability of the Romans (or the Tang, which employed similar tactics several centuries later) were not the norm.

The Mongols were more successful than previous steppe peoples for many reasons that it would take an expert to elucidate (not least the fractured political situation of their opponents), but their eventual conquering of the Song dynasty (1260-1294) showed that they were absolutely the real deal, if it wasn't already as obvious as the day by then.

However, in the military sense, the Mongols had all-but perfected traditional steppe tactics and were accomplished in basically all important fields of warfare. They utilised horse archery to an even greater degree than did most of their 'predecessors', and were able to maximise their firepower and the maneuverability of their steeds (their battlefield manoeuvre and unit tactics were incredibly skilled) to be even deadlier than other steppe peoples at the tactical level (May 130-1). Of course, the first Mongol conquests were of the steppe itself, so in expanding Mongolia they had to prove and finetune their, not unique, but qualitatively superior tactics against other steppe peoples, including powerful groups such as the Tatars and the Naiman Confederacy which the Mongols defeated and absorbed. In a sense, you could view them as the 'final evolution' of horse archery tactics at the stage they were active.

They were also extremely proficient at intelligence gathering, utilising an organised planning process, and at least in their initial conquests under Chinggis Khan, their armies coordinated very well (132-3). They heavily utilised psychological warfare to reduce their need to carry out lots of prolonged sieges, for which they were initially ill-equipped, but the Mongol willingness to absorb new ideas and experts from other societies meant that they quickly became very proficient at siege warfare too (132). Essentially, it was not only the horse archers, but every Mongol military strategy and operations were conducted with great skill and they were above all a highly effective military organisation, not just an awesome group of horse archers.

As others have said, until the advent of gunpowder the horse archer was essentially the dominant battlefield technology in the Mongol World and the best 'counter' was more horse archers. The victory of the Mamluk Sultunate at Ayn Jalut was impressive, but hardly a major blow to Mongol power, and this victory was mainly a result of the extreme individual skill of Mamluk horsemen (they were professional soldiers after all), their knowledge of their fate if the Mongols conquered them, and their superior leadership at that point in time (141). The Mongols' main enemies were pretty much always other nomad armies, considering the empire of Chinggis Khan and his successors didn't last that long and the successor empires, the Jochid and Chagatayid khanates in particular, began competing against each other directly (141). Anyone who wanted to fight the Mongols effectively needed to develop their own units of skilled cavalry, whether it be the Sultanate of Delhi (142) or the Rus (144). The Chinese, due to their experience with steppe peoples dating back to 3rd century BC, had sophisticated methods of dealing with horse peoples focusing on infantry, firepowder, and use of terrain and fortifications (Wright 57-8), but this didn't stop China from being conquered over and over by steppe peoples. The Chinese Ming dynasty kicked the Mongols out eventually by capitalising on the chaos of Yuan government at the time, but the Chinese never developed cavalry as effective as the steppe peoples, particularly the Mongols (59-60). Until the Qing dynasty (1644-1912) they were always vulnerable to powerful steppe confederations.

According to May, even with the advent of gunpowder the Ottomans were the only "gunpowder state" that managed to truly counter horse-archers effectively (152), but from the late 1600s when cannons became more common, they were very effective at disrupting the organised steppe cavalry formations (151-2). May unfortunately does not go into what made the Ottomans so effective, but I note that besides their traditional familiarity (as Turkic people) with steppe tactics, they had the resources of a sedentary state, a large corps of professional soldiers (the Janissaries) and were particularly adoptive of new technology and tactics (eg. gunpowder), so I think it's fair to assume that their ability to resist the Mongol successor kingdoms was a product not only of their great resources and traditional understanding of steppe-tactics but their relatively modern military.

Sources:

May, Timothy "The Mongol Conquests in World History", 2012.

Wright, David C. "The Northern Frontier" from A Military History of China, Eds. David A. Graff and Robin Higham, 2012, 57-79

Follow-up question : Apparently during their campaigns, the Mongols were defeated only once in a battle by the Mamluks of Egypt. What was different in this case?

I've answered essentially the same question or a related one a few times before here, here and especially here.

Keep in mind these answers apply mostly post-gunpowder. Pre-gunpowder it basically boiled down to hide in a fortress until they leave or employ other horse nomads. Alternatively, one could use armoured horse archers to some effect, as the Sassanids and Romans (and later the Byzantines if you are that way inclined) did, as far as I can tell.

If the mods would like me to rephrase one of my earlier answers here I'll try and find the time later tonight, but I think these links should suffice.

Follow up question. How did the Chinese infantry crossbow armies do against the Mongols?