Well it depends on the realmpool.
In my realmpool, Kotmogu is mostly a win on alliance side, but the mine is 99% a lose to the horde.
So it took me 2 Kotmogus, but more than 20 Mines to get them done while the quest was new. Most of the players (horde and alliance) were 8 out of 10 people in PVE gear. Out of those 8, half the players had raid gear and close to 400k life, the other ones had under 300k life.
One useful tip: Get 3 friends: a ranged, a healer and yourself as DD/tank/whatever with some decent PVP gear and nuke the shit out of everyone else. especially when you're in Teamspeak.