I'm quietly doing some work on a megadungeon and one of my main concerns as I design it is the factions. While I'm not yet at the point where I want to tell you exactly what the factions are, I do want to go through some ideas on broad types of factions that will exist.
The factions in B2 Keep on the Borderlands are primarily classifiable as tribes: kinship groups of humanoids organized around a single leader. The tribe is a basic, fundamental unit and can be used to describe basically any monocultural society with a strong leader, whether it's hobgoblins, berserkers, cavemen or hill giants. Typically they are not humans of the prevailing civilization. These are a solid form of organization and work well, although they shouldn't be the only type of faction.
A second type of common faction is the voluntary group. A cult, a group of bandits, or rival party, often made up of human or demihuman characters. There are two interesting factors about voluntary groups. One is that the characters in it will frequently speak Common, and therefore be able to negotiate, bargain and discuss with PCs. The other is that membership is an open question. You can do fun things like having a henchman or PC get Charmed by the evil cult and used to betray the PCs' cause. It's also possible to ally with or even join the voluntary group.
Related to voluntary groups are alliances. These are not as formal, and may actually be partly made up of a tribe or voluntary group – for instance, a tribe of goblins may have "pet" giant rats, or be enslaved by an ogre. These are not generally groups that are being recruited, and may form on more tentative lines than other factions. Player intrigue might be able to turn an alliance into two or three separate factions, while others may form in the face of PCs raiding the dungeon.
The specific form of the faction might also differ. These are a few ideas for how leadership is decided, each of which I'm sure has some variants.
Frequently leaders are assumed to be despots, absolute leaders who rule through violence or fear of violence. That can be plenty of fun, particularly if the faction uses "Klingon promotion" where a new leader rises by killing the previous one. There are several potential player hooks there – particularly if, in the style of A Princess of Mars, PCs actually find themselves as leaders within the faction.
But there are other methods. Maybe bandits will use a pirate democracy, where a leader is elected, and can be recalled (violently) if needed. Or there may be a cult of personality; I'm interested in the idea of having a charismatic leader in a dungeon who leads a sort of motley coalition by sheer charisma. Others might be a protection relationship, where a powerful creature or NPC leads weaker followers because it offers physical or magical defense. Some enemies will undoubtedly use slaves, which present a bit of moral dilemma.
As my own dungeon keeps growing, I'm going to develop several of these types of factions. A dungeon with sufficient factions, IMO, is rife for more roleplaying than even many city-based adventures. And it reinforces that my favorite type of roleplaying is the kind with the threat of violence behind it.