I see two problems here - optimizing the battle on the server and allowing the player to view and change the battle before it is finished.
First things first - optimizing the battles. You need to design combat in rounds, and roll dices for each unit separately within each round, giving you 20000 computations per round - each unit attacks one other unit and defends from one attack. You can design the combat system so that it will last a small amount of rounds, for instance a 100 for 10000-unit armies. If you find your battles take longer, you could make them more 'bloody' using various techniques - make combat between opponents more random (higher standard deviation), penalize fighting between the same 2 units for more than 2 rounds etc. This should give you a required total number of 'computations' in the millions per one battle of 10000 units, which seems sensible. Moreover, it is easily breakable down into smaller chunks or parallelizable from the other server work.
A different approach you could try is using Lancherster's laws for mathematically modelling battles.
Once you have that, you can look at your second problem differently. You can precompute battles and store them as a series of states, each state corresponding to a combat round. Displaying battles is, like many things in games, interpolation - you know in what timeframe each round should occur, so when displaying the battle at any given time you can choose the two nearest precalculated rounds and show to the player a dynamically-changing state that is somewhere in-between. You don't have to be precise; nobody is interested in exact numbers. If the player decides to retreat, you can confirm the action instantly and send it to the server, which will recalculate part of the battle - from the current (or next) frame onwards. If you give the player instant feedback, he will accept that the action is non-instantious and that there might be more casualties that the last displayed number (it's believable that receiving an order and retreating take time). Other events - reinforcements, change of tactics, spells/abilities etc - can all be handled in the same way, by recalculating the battle from the given moment onwards.
In essence, what I'm saying is discretize the battle, store it, interpolate for the purposes of showing it to the player and recalculate when a player decision is made.