Elenhel = Free wanderer's scroll every 30 battles + Mana recharge. That cannot be beaten by +700 leadership. The +4 Intellect is a good bonus, and it acts like a 5th slot for a weapon, without the need to equip it. Besides, his slots are not bad at all. As a mage, pumping up attack and hoping your troops will do the majority of the damage is not very efficient (albeit easily doable), because you are not a warrior and your leadership is low. Slap some good offensive gloves (the new gift bag has a bunch of those that boost intellect, mana or spell powr) or the gloves of necropolis in his slot and you will be just fine. The dress he can wear can be pretty much anything - the +1000 leadership one, the +2 Def/+2 Int, the +5% resist, or the dress of the magess if you can find it. Never underestimate Elenhel's slots
With the new gift bag, mage + elenhel can get up to 75 intellect before any shrine or other bonuses from game objects kick in.
The way you have it, the dilemma is whether to get +700 leadership or +4 intellect and +150 leadership. I would choose the latter any day
So, get Elenhel, pump up your intellect, put in some decent items in his slots and start utilizing the offensive spells