Freedom of Religion
Genghis Khan himself worshipped Tengri, the god of Eternal Blue Sky, but he allowed his followers to worship any religion they wanted. This helped keep the people living in land that the Mongol army has just conquered to have a smaller chance of rebelling.(Read more about this on "Explanations", number 6. Link on the bottom of this page.)
Genghis Khan actually gained more followers by giving religious freedom to his people, while most other big empires at the time did not. His followers included christians, muslims, shamans, taiosts, etc. That is how the this act gained Genghis Khan a lot of public support through religion.
Christians, Muslims, and Taoists joined the camp of Genghis Khan for his freedom of religion.