I like the idea of mercenaries going from 0th to 1st level through extended campaigning, but I don't like needing to have a spreadsheet of every mercenary unit's XP. It occurred to me last night that maybe a low-fidelity approach would work. At the end of a session where a mercenary unit earned XP from an adventure or campaign, compare that XP to the XP needed to level (for a 6-man squad of baseline 0th level infantrymen, a total of 600XP under ACKS). If the XP earned is greater than the total required, great, the unit levels. If not, convert it into a fraction of the XP required to level, then turn that into a probability and then into a die roll. So if the unit earned 300 XP, that's a 50% chance to become veterans, or 4+ on a d6. If the roll is failed, the XP is lost.
This works out about the same in expectation, but with a long tail; some units will level sooner, some later, some will get very unlucky and take forever to level. But that is rare. It does have the nice property that all units of the same type that got the same share during a single adventure will have the same probability of leveling, so you can just roll a big handful of d6s and count your successes.
You could probably also do something with casualties from veteran units giving a chance of loss of veteran status, as new recruits replace the old skilled ones, although as Von Schell notes in Battle Leadership, even a few veterans mixed into a green unit help a great deal in bringing it back up to veteran status. So maybe taking a bunch of casualties and replacing them makes a veteran unit fight as a regular unit for one adventure or so, rather than risking permanent reversion. Maybe if there are a bunch of casualties during that second adventure too, then it becomes a risk (but here we are again back at adding book-keeping, state, and memory across adventures).
Another potentially entertaining and even more ill-advised extension would be to have henchmen or even PCs level probabilistically, with the same procedure of "compare earned XP from this adventure to XP to next level, convert to fraction, convert that to a probability, and roll". But PCs already have a bunch of state associated with them, so tracking one more (XP) is not a great burden. It could be pretty funny for henchmen to level nondeterministically though; it would make "henchmen of equal or greater level than master" a more common occurrence.