First, consider a design that avoids the need for a virtual update entirely. The overhead of dynamic dispatch is trivial, but non-zero. More importantly, however, the fact that one is necessary generally suggests that you may have poor cache coherency in the storage of your units. That is, you may have something like a
vector<Unit *> which contains units of various concrete subtypes in effectively random order.
An approach where you store lists of concrete unit types and update each unit type in large blocks has better coherency, and avoids both the indirection needed for the dispatch and the dispatch itself. The outboard component entity architecture is particularly amenable to this.
Related, consider whether the type hierarchy for units makes sense: do you really need inheritance here, or can you instead compose the differences between units as data?
Second, use an appropriate spatial partitioning technique to determine which units are more important (for example, visible units are probably very important) and must have constant, immediate updates versus which units are far away and don't need as frequent updates.
Units with less priority can be updated less frequently, such as by subdividing them into N groups which are updated every N frames, effectively amortizing the cost of their update over multiple frames of update time.
There's no magic bullet: you basically need to make sure your updates are cheap (make sure you profile, so you know the updates are actually expensive, where they are expensive, and how to cheapen them) and that you do fewer of them (prioritizing the units that matter over ones that are less important).