The Mongol conquests were bloody, but they actually did not kill tens of millions. This factoid (I usually see a version of it saying that "Genghis Khan killed 40 million") has developed from a chain of citations that are originally based on demographic estimates from Ping-Ti Ho, especially his Studies on the Population of China, 1368–1953, published in 1959.

This was cited by J.D. Langlois in China Under Mongol Rule, who stated that the population was "steadily declining" over the Yuan Dynasty period (1271-1368), and notes that while disease no doubt played a factor (the Black Death swept East Asia in this period), "we require more information before the demographic mystery is to be resolved."

David Morgan cites Langlois in his history The Mongols and notes:

"Yet even in China we have to explain a drop in population, if the figures are right, from over 100 million in Sung and Chin times to 70 million in the 1290s and 60 million in 1393, after the Mongols had been expelled. The word 'disease' is much bandied about nowadays, and no doubt justifiably; but the suspicion must remain that Mongol policies and actions may have something to answer for."

So generally the 40 million number mostly comes from an estimated drop in the Chinese population of 30 million over the 13th and 14th centuries, and then a few million more estimated to have been killed in all the Mongol-related wars (which it should be noted stretched over a long time, from Temujin/Genghis Khan's first campaigns in 1187 to Timur's death in 1405).

I have more info on how this developed into a factoid in an answer I wrote here.