You also have the option of making the units-to-be-exterminated be something other than the fighters themselves.
-
Weapons. Weapons are consumed by fighting (break, left on battlefield when fleeing, captured somehow), and enemy has limited supply. If you fight long enough, they will eventually have nothing good to fight back with. You dont need to kill a single enemy to render their forces useless (at least until they find/manufacture replacements).
-
Ammunition. Same thing, except might be easier to bluff (you dont know how long they can fight back until they cant, but you will notice if they have nothing to fight back with).
-
Food, supply lines. If you cut these off, the enemy can at best hold position for limited time, inflict some damage and retreat, or throw everything at you and try to win. Whatever they do with the front line fighters, there is a time constraint, and they cant throw their full force at you if they cant even get to the fight.
-
Communication channels. Maybe you can feed false information, or block an attack command from ever reaching enemy units, eventually disabling the whole army. Would work mechanically (imagine enemy groups on the map being greyed out one by one as you 'disable' them), but probably need to combine with another approach if you want realism.
-
Escape routes. Perhaps the enemy surrenders or flees if you are about to surround/corner them (someone mentioned a similar mechanic implemented through morale, but it could be standalone as well). Some overlap with supply lines, and you probably need to fight your way through.
-
Time. Maybe the enemy cant fight over winter (or they need to get back to defend their capital before your other army gets there), so your goal is to just survive until they run out of units of time. Asymmetric, but should work.
-
Undefended paths. Whoever builds a complete 'wall' with no weak spots first, wins. Maybe at first the defenses can be torn down, but if they remain defended long enough (increasingly fortified) they become invincible (possibly with weaknesses like attacking from behind - but that wont work with a complete wall of defenses). Assume there is room for only one wall on the map, so stalemate cant occur.
All of these can be combined, or split into multiple levels/layers, to add complexity and strategies. Of course winning the battle doesnt mean much - the enemy can be stronger in the end, so balance that with some victory/loss consequences if necessary.
You really dont need to kill a single unit if the victory condition is in terms of some other resource or pattern (so you can freely determine how big the losses tend to be).