Whilst it's true the early Mongol Empire (when the Mongols predominately followed Tengrism) was usually pretty tolerant, especially under Genghis Khan and Ogedei. But it's important to remember the united Empire was very short lived, and for most of the Mongols existence they were ruled under separate khanates.

For instance, the Golden Horde did adopt Islam as a state religion in 1313 under the Khagan Oz-Beg, and after a bloody few years it became the mainstream. In the 1500s under the Mongol Yuan Dynasty (which includes the Mongol heartlands) Altan Khan favoured Tibetan Buddhism over the Tengri, and actually granted the Dalai Lama his title.

Three of the four states ended up embracing Islam, the fourth Buddhism as they adapted to rule over the non-Mongol population more efficiently, and that did lead to a more intolerant society. They were very pragmatic warlords who used religion to their advantage, the same as everyone else.

^{Ed: Reordered sentence to make sense.}