To tackle this, I want to first explain what the native Mongol religion was, then why it didn't supplant local customs. Because you're right: the Mongols had a high opinion of themselves (and they did conquer the largest land empire in history, so that seems justified), yet their cultural legacy doesn't measure up to the legacies of other great empires.

One of the manifestations of a sense of superiority is that the Mongols were largely disinterested in telling anyone else about themselves. We have very few texts written by Mongols about Mongols, particularly from anywhere near the 1200 CE time period that people tend to be interested in. However, we do have the works of some outside chroniclers. In the case of religion, we are particularly lucky, because most of the visitors to Mongol lands were missionaries, who naturally took a great interest in the indigenous customs. I'm going to be relying here primarily on the chronicle of William of Rubruck, a Franciscan missionary who visited Mongke Khan in 1254. This is the perfect time period, because it captures the beginning of the transition from the pre-1200 wholly animist tradition to a kaleidoscope of practices from different faiths.

When they were one of many relatively unimportant nomadic groups living on the steppe, the Mongols practiced a shamanic tradition called either Blue Sky or Tengriism. The practices are roughly what you would expect: Rubruck mentions a sort of blessing ceremony where

And when they have come together to drink, they first sprinkle with liquor this image which is over the master's head, then the other images in order. Then an attendant goes out of the dwelling with a cup and liquor, and sprinkles three times to the south, each time bending the knee, and that to do reverence to the fire; then to the east, and that to do reverence to the air; then to the west to do reverence to the water; to the north they sprinkle for the dead. When the master takes the cup in hand and is about to drink, he first pours a portion on the ground.

What is more important, in terms of your question, is the power of the religious structure underpinning these traditions. Because Mongolian shamanism was very much not an individual practice, as Rubruck makes clear when describing the priesthood.

Their diviners are, as (Mangu Chan) confessed to me, their priests; and whatever they say must be done is executed without delay…. They predict lucky and unlucky days for the undertaking of all affairs; and so it is that they never assemble an army nor begin a war without their assent, and long since (the Mo'al) would have gone back to Hungary, but the diviners will not allow it… All things which are sent to the court they take between fires, and for this they retain a certain portion of them… These same diviners disturb the atmosphere with their incantations; and when it is so cold from natural causes that they can bring no relief, they pick out some persons in the camps whom they accuse of having brought about the cold, and they are put to death at once.

It's not hard to see what's happening here, or parallels to innumerable other places. You have a class of priests using their spiritual power to exert temporal control over the society, making themselves indispensable to the political leadership, profiting from their position, and eliminating dissenters on pretext.

Now, this is all well and good as a governance structure for a nomadic, clan-based nation of a few million people on the outskirts of civilization. And up to 1206, that's what the Mongols (and other associated ethnic groups like Merkits, Naimans, Tatars, etc.) were. But the following 50 years saw the incredibly quick expansion that put the Khans at the head of nearly all of Asia. Conquering that territory had been, well, not that hard--the Mongols were a true military superpower. But administering it was a much greater challenge. We've already seen their extant tax system, where small clans sent offerings to the Khan which were divided among the shamans and the family of the Khans. That was wholly insufficient to administer a continent-spanning empire.

So the Mongols did what they did best: incorporated the advances and innovations of other groups into their own procedures. One of our other best contemporary sources on the Mongols, Juvayni, was a Persian born in Khorasan (part of the Khwarezmian Empire). His grandfather had been the Minister of Finance for that empire, and when it was conquered by the Mongols, Juvayni's father took up the same post for them. Stories like that of Juvayni were commonplace in the Mongol Empire, as the Khans supplemented their pitiful lack of capable administrators by leveraging local populations.

This is the key context for the Mongols' otherwise surprising religious tolerance. Mongke tells Rubruck that

But as God gives us the different fingers of the hand, so he gives to men divers ways [to approach God].

Karakorum was home to many religious buildings and a cosmopolitan culture of people drawn from all corners of the vast Mongol Empire. And in fact, Rubruck even participates in a religious debate at the imperial court in Karakorum, where

We were assembled then on Pentecost eve at our oratory, and Mangu Chan sent three secretaries who were to be umpires, one a Christian, one a Saracen, and one a Tuin; and it was published aloud: "This is the order of Mangu, and let no one dare say that the commandment of God differs from it. And he orders that no one shall dare wrangle or insult any other, or make any noise by which this business shall be interfered with, on penalty of his head." Then all were silent. And there was a great concourse of people there; for each side had called thither the most learned of its people, and many others had also assembled.

The existence of debates like this and the broader atmosphere of tolerance were, I would argue, far more a pragmatic decision than one rooted in a spirit of religious benevolence. The Mongols were most assuredly NOT "tolerant" in an Enlightenment sense--they frequently made example of places that dared resist their temporal authority, and I don't think I need to enumerate examples of that aspect of their conquest and governance. But once an area was conquered, the Mongols found themselves dramatically outnumbered by the local population. Religious authorities represented both local leadership figures, and part of the cultural elite who could perform the functions of administration. Given the choice between alienating the leaders and the populace by forbidding their religion, or incorporating them into the administrative structure of the empire, the ever-pragmatic Mongols made the sensible choice.

The effect of this, as you may have gathered, was that while Mongol military authority could be and was imposed, Mongol cultural authority could not be. Without a sufficiently large group practicing the religion in a foreign land, the diffusion of shamanic practice via relationships (i.e. converting before marrying someone's daughter) was tremendously slow. And with the Mongols willing to employ anyone, regardless of their religion, so long as they were a competent administrator or general or what have you, there was no incentive to convert as a means of "getting ahead." Instead, local religious customs persisted and flourished

Across the generations, this had a profound effect. As the empire fragmented into Khanates dependent on local power bases, conversion to the local religion was an increasingly attractive and pragmatic choice. Khans needed to administer their territory and to field armies that could defend that territory from rival Khanates. Both of these tasks were made easier by having a common religion with the populace. It is of course impossible to know how many of the original conversions were motivated by pragmatism instead of a genuine religious faith--but certainly by a few generations after conversion, the Mongol leadership of (for example) the Ilkhanate would have grown up in a Muslim tradition, and held those beliefs as sincerely as any other person. That of course can range from a fervent believer to someone who only pays lip service, and that entire range was present across all of the Khanates, but the trend was very certainly towards at least some embrace of the local religion on the part of the Khans and their courts.