I actually wiped 4 times at level 60 against him with 5x shamans, and gave it one last go before giving up and killed him on the 5th try. This was with using both blood fury (+125 dmg orc racial at level 60) and elemental mastery.

Unless the ally quest is different from the horde quest, he doesn't summon earth elementals he summons infernals (much worse).

Anyway, on the fifth try I killed him right as he summoned the infernals, then they killed one of my guys before despawning. He didn't really use much magic against me, just physical attacks which could 2-3 shot my guys. Basically spread my guys out a bit, tried to force aggro to stay on my main using frost shock, and timed one heal between each lightning bolt, which seemed to work pretty good. Not much to say other than that, DPS as fast as you can (start with ele mastery LB + CL, then spam LBs and lesser healing waves or chain heals if needed). It was the toughest thing I had to do in hellfire peninsula by far, even harder than the first two bosses of Ramps.

Also, one thing that will help immensely is to do the maghar quest (wolf spirit), then go back to thrall, then go back to maghar and do the 2 quests which net you a good caster 1H mace, combine that with the shield reward from one of the first few HFP quests and having a shield on all your shammies helps a TON against any physical attacks. I had to do that to beat the first boss in HFC.