Firstly, a problem is that figures are greatly exaggerated. The Secret History of the Mongols (for some information, the most reliable source) lists there being 100,000 men in Genghis' army in 1208 so it seems unlikely that that number doubled in a few years. Of course, each of these men had three or four horses so the biggest problem was pasture rather than food. The men were expert hunters due to the nomadic lifestyle in Mongolia. So as long as the army continued moving they could strip the land where they were and by the next day have reached fresh pastures and hunting. The Mongolian army was organised into decimal units; the smallest being the Arban, which was ten men that comprised a mini family. Timothy May's The Mongol Art of War suggests that each Arban was responsible for ensuring that they had a goat and two sheep as well as their other rations before the march. In times of emergency the goat milk could be added to a little blood drained from the horses not in use to create a protein high mixture that would sustain the army. This is only a surface look at Mongolian logistics and I can try to answer any more questions if you want.

The mongols were nomads that lived of cattle like sheep herding. So they brought all their sheep and horses with them as a large stockpile of food when they set out to counquer china. They did plunder quite a bit of food as well during their conquest so finding food was probably not too hard for them. Findning water for such a large group of people was probably harder since they had most likely had to cross the Gobidesert (north of china). They just refilled their supplies whenever they came upon drinkable water.

Scouting the land in front of their army was also probably crucial to be sure they would find someone to fight and new sources of water and food.