I'd rather use the "at least X more HD than the ally." Warmongers should be able to lead entire armies, and if we give this ability a total HD cap they might have trouble inspiring more than a platoon.
Haven't decided yet how much fewer HD the ally should have. I was originally wondering about +4, but that was just because I thought Warmongers had 10 hit dice (I was getting my Tasked Genies mixed up).
+2 is OK but it seemed a little high to me. I preferred +3, which is enough for the Warmonger to inspire 4th level heroes and stock Ogres.
However, I'm not that bothered about it, even +1 would do in a pinch.
Revising...
Inspire Troops (Ex): A warmonger genie can use displays of military prowess to inspire courage in its allies and followers, bolstering them against fear and improving their combat abilities. To be affected, an ally must be able to see the warmonger genie, and the warmonger must have at least X more HD than the ally. The effect lasts for as long as the ally can see the warmonger genie and for 5 rounds thereafter. An affected ally receives a +2 morale bonus on saving throws against charm and fear effects and a +2 morale bonus on attack and weapon damage rolls. Should the ally see the warmonger genie be defeated or slain the morale bonus from Inspire Troops changes into a -2 morale penalty that lasts for 10 rounds. Inspire troops is a mind-affecting ability.