I like this story line, so let's see what we can do:
The first decision is how you want the undead army to potentially behave. Do you want them to be able to carry (some) of their undead army into combat with them? If so then I suggest "Nulathoe's Undead Army" as suggested in this answer: How can a character create a skeleton (or any other undead)
There are also some other existing spells/abilities that fit this general purpose: http://www.giantitp.com/forums/archive/index.php?t-269010.html (Wizard, Invoker, Mage, Nethermancer abilities) There's also the item "The Girdle of Skulls", a waist-slot item that is said to summon undead for the wearer to command.
In general, the Nulathoe's Undead Army seems to be the most interesting, as written it gives 5 undead in a balanced way - you have to use a minor action to give just one a movement, but if one attacks then all the others will attack automatically if in range.
Of course, this is not usable by a Paladin directly as a skill. RAW, Paladins don't do this kind of thing, Mages/Wizards (Necromancers) do, so I suggest using these items/spells as a guideline/suggestion; you'll likely have to roll your own item or permit some special skill/feat of your own design if you want to go that direct route.
Build vs Acquire
Sure, you can build an army, but you could also just steal one someone else went to the trouble of building.
To build, you might be using artifacts/scrolls/rituals to build up a cache of servants, or it could be as simple as a single relic or even alteration of the Nightbringer itself that permits something like Undead Army to be used; ostensibly the army is to serve your paladin, but perhaps Nightbringer needs a Plan B if his servant doesn't stay dark enough for its tastes?
If you go the item path, I suggest a "down side" - perhaps a relic that can do the job, but it needs something to fuel it, perhaps something that pushes your player's willingness to truly have his own army? Fueled by the agony of innocents, or screams of terror, tears of virgin priestesses, or just good old fashioned blood rituals that will have to attain a ghastly level of volume to build a suitable army. The road to hell is paved with good intentions, and nobody goes straight into being a sadistic monster - give him a little power, but make each additional act of army building test his desire. He can choose to give up the potential power, or be lured into a never-ending path straight into the heart of darkness. Maybe he changes his mind at some point? Lots of possibilities!
Mechanically, each encounter could be standard encounters/battles/RP scenarios, something you could potentially work into a regular crawl (hold on guys, don't finish off that wizard just yet, I need a little something before he dies...or hey, why free that prisoner to probably just get killed on the way out of here, when their life could serve a grander purpose?).
If that doesn't suit your fancy, you can follow the lessons of army-builders throughout history - just steal it! Perhaps a depraved would-be-conqueror was buried along with his army and you need to destroy his source of power to disable the threat, or he could find a way to get the army to follow him as their new true master (undead are generally dumb, so maybe that's not so hard - maybe its harder than it looks). The common tropes are amulets, stave with some special insert, book/tome, secret words/incantations, etc.
Perhaps you can do it piecemeal, representing the army building as individual domination of "undead captains", and each one seeks to be spared of eternal damnation by joining "the cause"?
With each option you can decide to let things go badly, like a captain who can't be convinced and must be killed, or a ritual that fails and leaves him or the party beset by demons or zombies, or a dark intent being revealed by a prisoner who escapes the torture of his dark machinations. Relics can break, lies can be told that cause an undesired outcome if believed (Nightbringer I'm sure would be happy to throw in some bad advice or self-serving 'help'), and there can be consequences that force reconsideration.
If there is a (set?) of dark relics that give command of an army, people are going to want to take it for themselves, and perhaps to send a message and avoid constant harassment the time comes for the paladin to make a grim, excessive example of what happens when they get in his way. Perhaps it all becomes too much, the cost is too great, and he wants to destroy this evil before its too late.
Maybe the army is too much, and he risks madness, delusions, domination, or releasing an evil far greater than anticipated. Or maybe the cost of maintaining the grim magic outstrips his urge to build his army, and he must chose to commit a growing atrocity or face losing control completely.
The other thing you must consider is the implications to your normal play. If he really does go full dark side and gets even a small army, is there any RP-reason he can't send them off willy-nilly to invade a dungeon? Nulathoe's UA provides a relatively balanced mechanic of trading a powerful spell (healing surge) to cast, 1 HP undead allies, and the action restrictions. If you go that route, make him pay something similar, perhaps from a Paladin ability equally useful to healing surge to power it.
Its reasonable that, not being a super Archlich himself, his ability to usefully manage undead is limited, and so he could even potentially have an army of thousands of lumbering undead, but anything more than "lumber that direction and eat anything that gets in your way!" could be just too much, and is thus utterly unsuitable for smaller scale encounters.