I've been thinking about this feature for a bit. It would be one of the nicest new abilities to add, and should be possible to implement if player teams can be changed during a game. This is how I believe it should work:
The ability to change alliances should be a game option, possibly disabled by default. When enabled, a menu (opened by a keybind) presents the player with a GUI listing all players (including them self). They can select any players from that list, while another selector specifies the team in which he suggests moving (more on that below). There should also be a text field where the player optionally writes why they want the team change. Lastly, when the player is done he presses ok and the proposal is sent to all players involved (more on that below).
The menu can be used to do one of two things: Go to another team, or ask someone else to join yours. The menu should assume which you are doing by the team you selected (if it points to your current team it means you're inviting, if not it means you want to leave there). When you want to join a different team, you can select either just yourself or yourself plus other players (be they enemies or allies). When you want to bring a player to your team, you can only select enemy players. Once the player presses OK, all players involved get notified and must express their approval (either in chat or a menu popping up). That includes the players you selected to invite / leave with, as well as all players in the team you are inviting to / leaving to. The change only happens if everyone votes "yes".
To better explain what I had in mind, here are some examples of how it would be used. Given the following initial setup, and considering we are Player 1:
Player 1 = Team 1
Player 2 = Team 1
Player 3 = Team 2
Player 4 = Team 2
Player 5 = Team 3
Example 1: Players 1 and 2 aren't doing too well. Players 3 & 4 are more powerful but could use some extra help. In order to survive, Player 1 considers betraying 2 and joining 3 & 4, so he launches the proposal of joining Team 2. Players 3 & 4 who compose this team are informed, and need to vote whether they agree or not. If both do, Player 1 becomes part of Team 2. In this circumstance, Player 1 could have also invited Player 5 with him, and if 5 also additionally agreed both of them would have went to Team 2.
Example 2: Players 1, 2 and 5 are very weakened, while Player 4 is very powerful. Players 1 & 2 can no longer afford to fight 5 as well, and neither can 5. So Player 1 proposes that Player 5 joins his team, and 5 is asked to vote if he wants to or not. Player 2 is must also vote since he's part of Team 1 where 5 is being invited. If both votes are positive, the transition is done. Additionally, considering that Player 3 was willing to betray 4 for whatever reason, the proposal could have been that players 5 and 3 both joined Team 1 (3, 5 and 2 would all have to vote if they agree).
Example 3: Player 1 has grown very powerful and all other players are weak. He's actually so powerful that he no longer wants any allies. Although the game started with 3 teams, he makes the proposal of becoming part of a new team (Team 4) so he may separate from everyone. Such would require no vote from anyone else since it involves Player 1 alone. Optionally, Player 1 could have invited any of the other players (2, 3, 4 and / or 5) to come with him to the new team.
Example 4: Player 1 is being attacked by Players 3 & 4. He's losing and near the point of being destroyed. Before the enemy's units get to his last castle, he asks to surrender, by telling players 3 & 4 he wants to join them. If 3 & 4 feel like taking 1 as an ally instead of finishing him off, they accept. Player 1 becomes part of their team and the units from 3 & 4 automatically stop the attack.
I think this ability would add more feel, strategy and realism to MegaGlest. What led me to think of this were historical movies I occasionally seen recently... about how nations went to wars, established alliances, surrendered when there was no other choice, etc. Only downside is that this could cause imbalance, as weaker players would try to join the stronger ones. Then again, that's how many weak nations survived throughout history, so this would only add more realism. What do you think? Can this be done in MG anytime soon?