B) Wagon treks (and for the RPG-like setting it would probably sufficient realistic to just conquer some oasis or three a few dozen miles away); for the overkill-solution see below.
It does not have to be perfect, I doubt that neither Redcloak nor Xykon would mind a few hundred or even thousand dieing each month due to the bad situation they are in.
"Cannot be done" is a very strong claim in a RPG-Fantasy like setting, especially if Redcloak has access to a daily or weekly Gate spell to the Elemental Plane of Water. He can turn entire acres of desert into lakes if he wishes to.
(A 20 ft disk is 29,22 m², assuming a flow of 1 m per second (from the elemental plane of water this is not too far fetched, that is 30 m³ per second, and he has a duration of some 17ish rounds (rounds per level, each round is six seconds).
Redcloak can get ~3000 tons of water per cast - I doubt water is an issue at all )