I've been intrigued with this story for a while now, if only because of its Indiana Jones-esque air of mystery. The legend has many different variations but, essentially, it states that after Genghis Khan died, his body was buried in a tomb with all of the riches of his plunders (treasures that were from the far corners of Europe and Asia and worth an unimaginable sum of money) and the slaves that buried him were killed by soldiers and those soldiers were in turn killed when they returned to the cities--in order to keep the location of his tomb a secret. How likely is this story to be true? If untrue, why haven't archaeologists been able to find Khan's tomb?
Also, do we know what such a tomb would look like based on, say, the tombs constructed for his ancestors/descendants? Was it common for rulers to be buried with their riches in 13th century Mongolia?
In summary, its highly unlikely to be true, and Genghis Khan never had a tomb that would be visible.
Firstly, that legend has common features with many 'dead barbarian conquerer' stories (you will hear similar stories about Alaric the Goth and Attila the Hun, among others). Some elements are plain unrealistic (killing lots of people of your own tribe isn't really practical in a nomad society).
The key element of Genghis Khan's burial (and this applies to many of his family) is that it was secret. One result is that even today the government of Mongolia does not support archaeological expeditions looking for his burial place (and suffice to say Mongolia is sufficiently vast and remote that looking freelance isn't practical). Histories at the time simply mentioned that Genghis (and other rulers of his clan) were buried in the Khentii mountain range (the place of his birth). As an aside, no history at the time suggests that any visible tomb was built for Genghis - in fact quite the opposite, that it was unmarked - and no history mentions burial goods.
The Secret History of the Mongols says nothing about Genghis' burial - it just skips from his death to Ogedai's election. The Yuan Shi, the history of the Yuan dynasty says that rulers were buried and the earth was replaced 'in order' and any excess was carried to places far away. A European observer in 1240 wrote 'they fill up the pit... and place over it the grass as it was before, so that the place should be impossible to find afterward'. There is a Song record of people who thought they saw his burial place (of course, there is a high risk they were being lied to) - it however starts with 'Mongolian graves have no tumuli. Horses are allowed to trample the area until it is as flat as its surroundings.'
(One will add that none of the above has not stopped people from claiming at least three possible sites for his burial)
Source: Man, J The Mongol Empire