What I did was accept the Alliance with the Mountain Clans at the start of the scenario, then let their troops go south through the pass first to serve as cannon fodder by blunting the initial assault. It's important to capture the city near the pass and use it as a bastion/rest stop for your troops. The Legions seem very overconfident and like to attack you even in cities, so take full advantage of that 30% armor boost from a level 5 city. (Pre-cast Holy Armor on your hero as well for a massive 50% armor boost that more often than not, when combined with a Patriarch unit, lets you easily outheal any damage during the fight.)
Once the initial rush of the Legions troops have been thinned out, you can start making forays into the southern area and claiming cities one at a time. If you can afford it, the hireable Dragons from the mercenary vendor make for a very powerful army too.