I happened to try a quick experiment last night when I rolled up my new shammy's on Mag.

I leveled 1 shaman solo to level 6 in about an hour.

I leveled 2 shamans grouped to level 6 in about an hour and 5 minutes.

My supposition is that anything more than 2 is going to "slow you down" because 2 still lets you do collection quests relatively easy (thus you can follow the guide's to the letter and be on target).

HOWEVER

Keep this in mind. When you are leveling 5 (or even 3 or 4) guys together it does take longer, but you are getting FIVE CHARACTERS leveled up. If I had leveled all 4 of my shammy's solo up to level 6 it would have taken approx. 4 hours. If I had done them in 2 groups of 2 it would have taken 2 hours and 15-30 minutes. I did 1/2/1 and it took 3 hours and 5ish minutes.

I think (and this pertains more to those fast levels early on) that duo'ing may be the way to go early on, but once you get up to 8 or 10 run them all together. Maybe do a duo and trio if you are 5 boxing and see how the times compare. Those first few levels are lots of collection quests that are too easy to pass up.