Let me make this explicitly clear from the beginning that Jack Weatherford's book is a good introduction to the Mongols, but Weatherford gets fanatical. It is not the end all, be all source on the Mongols. There are key points in the work that have been contested. Again, if you just want to read a novel-like history of the Mongols, this is the book for you. If you want a critical, well-sourced book on the Mongols, the book list has several which are good.

So, you want to learn about the diet of the Mongols? First, you should know what the diet of a Mongol warrior on campaign looks like. We'll address the second part of your question at the end.

Mongol Warrior's Diet

Dr. Timothy May cites a study which said that 3,600 calories of food were necessary for active Mongol males in a day. This figure is what is estimated to be necessary to ward off starvation and malnutrition. Each man carried his own rations and his arban consisting of ten men carried three and a half dried sheep and a cauldron with which to cook the meat. Standard rations were one skin of water and a paste made out of powdered milk.

Sources of Food

The preferred drink of the Mongols was something called kumiss. It is fermented mare's milk. William of Rubruck, a Flemish Franciscan missionary, observed the making of kumiss.

He [Rubruck] described how milk was poured into a large leather sack and then churned with a specially crafted stick or club, the head of which was hollowed out. Part of the mixture turned to butter, and the milk fermented and soured. The butter was then removed. More churning increased the fermentation and produced a clear and more potent liquor.

Dairy products, such as kumis were a large part of the Mongol's diet. Timothy May estimates that a mare produces roughly 2.25-2.5 quarts of milk per day above what is necessary to sustain offspring. Mare's milk is roughly 20kcal/oz which means that 2.25-2.5 quarts of milk can sustain someone for 1,400-1,600 kcal/day. That's about a third of the 3,600 calorie diet of a Mongol soldier.

In addition, they prepared a paste made of milk called qurut. This paste is made from powdered milk. When necessary, usually during winter when milk was not as abundant as usual, the paste would be put into water, blended, and drunk. An estimated 10 pounds of dried milk is taken on campaign. The same study cited earlier says that this form of ration provided at least 800kcal and 80 grams of protein. Again, another large chunk of the 3,600 calorie diet.

If dairy meals such as the ones described above were not available, the Mongols would boil millet in water to make a thin soup-like mixture. This provided nutrition. Usually they would eat some meat, probably sheep, with this soup. William of Rubruck also described what happened when a horse or ox died on campaign.

If a horse or oxen died they promptly dried the meat or made sausages;some they ate there and then, and the rest were smoked for later use.

Meat was prepared by boiling in a cauldron with salt and some water. This stew was called shülen. When meat was available either from a dried sheep or from something obtained while hunting, this was the main means of cooking it. The Mongols didn't have many other ways of preparing meat other than boiling while on campaign.

Another interesting fact is that the Mongols also used the blood of their horses to sustain themselves. This sounds crazy and I think it just might be. Marco Polo observed the following:

When they are going on distant expedition they take no gear with them except two leather bottles for milk; a little earthenware pot to cook their meat in, a little tent to shelter them from rain. And in case of great urgency they will ride ten days on end without lighting a fire or taking a meal. On such occasion they will sustain themselves on the blood of their horses, opening a vein and letting the blood jet into their mouths, drinking till they have had enough, and then staunching it.

It sounds crazy, right? Well, Timothy May did the research on how many calories come from a pint of horses blood! He estimates that a horse can donate one third of its blood without any serious health risks. You can reason that the horse will be fatigued, but major health effects would not be a factor here. That means that a horse can provide about 14 pints of blood, each pint can supply 156kcal per pint. So, approximately 2,184 kcal or almost 2/3 of the 3,600 calorie diet of a Mongol. Each soldier took between 5-8 horses with them on campaign. The maximum eight horses could supply a warrior with approximately 6 days of full rations. Timothy May does note that this would take a toll on the horses and it was probably used as a last resort, not as the first choice when looking for food.

When cereals were available, they were used to thicken soups or as a porridge.

Hunting

The Mongols supplemented their diet with meat from hunting. Not only did the Mongols hunt for food, they also used it as training exercises. The Mongols hunted various animals including marmots. Marmots were a key source of nutrition. A marmot weighs approximately 10 pounds and have 3.3 pounds of fat on average. Each ounce of fat is 250kcal, with a total of 13,200 kcal. The meat portion provided 3,400 kcal. This is approximately 5.5 days of ration per marmot.

Supply Lines

Supply lines for food were not necessarily needed for the Mongols, but they did need other supplies. The Mongols utilized Bactrian camels, which can carry between 200 and 240 kilograms as a pack animal and 400-600 kilograms as a drought animal travelling at 30-40 kilometers per day.

It should be noted that the Mongols didn't always travel in a great hurry. Usually, the bulk of the army could travel at a decent pace while the forward units or vanguard could travel very quickly to the destination.

Conclusion

I can't speak to the diet of the enemies of the Mongols, but I don't think that this is the key reason that the Mongols were successful. They used psychological warfare, innovative tactics, an advanced communication system, the restructuring of the tamma system which allowed the Mongols to hold on to newly acquired territories and others.

EDIT: Sources and formatting.

Sources and Additional Reading

The Mongol Art of War by Timothy May

The Empire of the Steppes: A History of Central Asia by Rene Grousset

The Mongols and Global History by Morris Rossabi

The History of Mongol Conquests by J. J. Saunders

In part what allowed the Mongols to remain so mobile was that their diet included a large amount of mare's milk, as well as in more desperate situations, horse blood. This basically meant that their transport and food supply could be one and the same for limited periods of time (supplemented of course by other foods), which greatly streamlined their logistics. Considering that the Mongol's true ace in the hole was their stunningly fast strategic level mobility, not just tactical, it would be fair to say that diet and food supply played a significant role in what they were able to accomplish. You actually see the same phenomenon with the Eritreans in the Eritrean war of liberation. They heavily relied on the camel, which not only is a fantastic pack animal, it also turns stagnant water into a sweet, nutritious milk. This helped keep them light and mobile, which is crucial when facing against larger, better equipped enemies.