How the hell do they feed the armies in randland?

Fielding massive armies like the ones in WoT are quite feasible actually. If you look historically, armies much larger than this have had similar long conquests.

In B.C. times, the Babylonian army that conquered the Middle East/Mesopotamia region supposedly had over 1 million solders.

The Persian Emperor Darius' army that invaded Greece was said to have between 200k-600k men.

The Roman Legion at its peak held at minimum 400,000 soldiers (there's an interesting discussion here about it http://www.worldaffairsboard.com/ancient-medieval-early-modern-ages/44182-how-big-were-ancient-medieval-armies.html)

In A.D. Attilla the Hun's army was said to have 200,000 troops.

In the American Civil War, the Union's total military might was over 1,500,000 and the Confederates were said to have around 1 mil. There were several armies going around with hundreds of thousands of men.

I have no clue how they did it, but the point is that they did, and some in more primitive times.