There's plenty of evidence in OD&D that all humanoids - not just PC races - can advance in level. Every humanoid race has extra-HD leaders. I'd kind of like to extrapolate those rules and apply them to all monsters.
the OD&D rules
Let's start by looking at the human baseline. In OD&D, bandits, berserkers, brigands, dervishes, nomads, buccaneers, pirates - basically all humans - use the same rules: for every 30 there is a bonus 4th level Fighting Man; for every 50 a 5/6 level FM; for every 100 a, 8-9 FM; if 200 + there are chances for wizards and clerics. That's a lot of characters with levels.
Humanoids use much the same rules but their leaders are frequently statted as the next strongest humanoid type: 40-400 1-1 HD goblins have 5-30 leaders with the stats of 1+1 HD hobgoblins; 20-200 hobgoblins have 3-5 leaders as 4+1 HD ogres; gnolls have troll-like 6+3 HD leaders; and orcs have complicated rules giving chances per 100 orcs of having actual monster leaders: ogres, trolls, balrogs, dragons, or level 7-11 fighting men and wizards.
How about demi-humans? For every 40 dwarves/gnomes there's a level 1-6 fighter. For every 50 elves there's a 2-4 F/2-5 MU, and for every 100 there's a F 4/ MU 8. Pretty wimpy compared to humans, but that's to be expected in a level-limits world.
That's all the monsters that come in groups of more than 100. They all have powerful leaders, usually many HD higher. We can assume that all intelligent races introduced in later books/editions should be treated the same way. And furthermore - and I find this idea exciting - probably every species has exceptional individuals, but since the number typically appearing is so low it's not worth it to detail them. But if you ever did get 100 15-HD Purple Worms together, maybe 1 in 30 would be 20 HD, 1 in 50 would be 25 HD, and 1 in 100 would be a purple worm 30/Magic User 11.
boiling it down
The OD&D rules feel right power-wise, but I don't want all sorts of lookups. I want a memorable rule that I can apply on the fly to 20-person bandit camps, 1000-person church heirarchies, armies of 10,000 - any vaguely meritocratic force.
After working at this for a while, and rejecting all sorts of things - every 30 of these gives you this, every 50 of those gives you that - I found that there is no universal best fit, and I realized that I didn't really want to be dealing with 5 different power levels in a bandit camp anyway. I basically want two things: a bunch of lieutenants and a leader.
The monsters with powerful leaders (humans, orcs) have about +8 HD per 100. Let's extrapolate from there:
In every double-digit group of creatures, the leader has +4 HD. Add +4 HD per extra digit.
That sounds pretty good, and it's reasonably scalable. In a barbarian horde of 100,000 (the size of Genghis Khan's and Tamerlane's hordes, and probably the largest reasonable in a dark ages world) the leader would have +20 levels.
As for officers, I don't want to deal with Tamerlane's 10k corporals, 1k sergeants, etc. Let's just do the leader's important bodyguard/lieutenants. According to OD&D rules, a group of 100 humans has 5 sub-leaders around 5 HD; hobgoblins and orcs might have half as many. Extrapolating:
Every leader has 1d6 lieutenants who are 4 HD weaker.
In practice, this rule means that only groups of 100+ have lieutenants with bonus HD; groups of 10-99 just have the leader. Good. Every 10 orcs doesn't need a giant chain of command.
There are much higher-level guys acting as OD&D leaders - dragons leading 100 orcs, for instance. Anyone can go slumming. But I propose that, in D&D, you need officers and leaders of around this minumum level to keep a non-civilized tribe or mercenary army running. (Civilized armies and countries can be ruled by level-1 leaders, which is both civilization's weakness and its strength.)
A fun repercussion: around level 5, PCs should be able to keep 10+ hirelings in line. At level 9, they should be able to command 100+ troops - which they can! That's around name level, when 1e fighters automatically get armies numbered in the hundreds.
Now let's apply this to all D&D encounters. Throw a fireball into a room of 30 orcs, and one of them might survive. If you run into 10 hill giants, one of them has stats more like a cloud giant. Watch out for the shambling minotaur in the zombie horde. And if you're pursued by nine 4-HD wraiths, chances are that one of them (the Witch-King) is a 8 HD badass.
OD&D freely uses different races as leaders. Orcs, for instance, have ogre lieutenants and human leaders. Make an army more interesting by swapping any lieutenant/leader with a monster or human of around the requisite HD. Thus a hundred elves might count 4-HD centaurs among their lieutenants and be ruled by an 8-HD ent.
How to level up monsters
So far I've mostly been talking about OD&D. Leveling up monsters in earlier editions is easy - add 4 HP/level and have them use the appropriate attack matrix - and 4e is easy with Monster Manual on a Business Card. But these days I mostly play 5e, which uses monster creation rules I haven't internalized yet. Here's how to make leaders and lieutenants in 5e. We'll be using Challenge Rating instead of Hit Dice.
From consulting the "Monster Statistics by Challenge Rating" chart in the 5e DMG, and adjusting it based on actual monster stats in the Monster Manual, it's clear that, up to about CR 20, AC and attack bonus go up a little under 2 every 4 CRs, HP goes up 60, and damage goes up 40. Feel free to use those stock numbers. I'm going to tweak them all a little to my taste.
AC, attack bonus, skills, saving throws, and checks: I'm going to bump this up to +2 every four levels: exceptional monsters who made it to high level probably have extra-good starting stats too. Besides, I want the difference to be noticeable.
HP: Most horde monsters are going to be Small or Medium and thus use below-average Hit Die sizes. Let's reduce the standard HP bump to 40 every 4 levels for typical horde leaders; double this for large monsters.
Damage: I love that big +40 damage swing per four levels. PCs will feel the weight of that. The DM can decide how to assign that damage, but an extra attack per 4 levels is a good place to start.
So here's how to add 4 CR levels to a 5e monster:
+40 HP (or +80 HP if Large or larger), +40 damage, +2 everything else (AC and all d20 rolls)
OK, let's put all the rules together into a bite-sized rulelet:
Monster Leaders up to CR 20
In every double-digit group of creatures, the leader has +4 HD. Add +4 HD per extra digit. Every leader has 1d6 lieutenants who are 4 HD weaker.
Adding 4 levels in 5e: +40 HP, +40 damage (+80 for Large), +2 everything else (AC and all d20 rolls)