Are there no common computations among compression algorithms?

It doesn't really matter even if there are, in the case of hardware implementations -- because hardware decoders/encoders are typically fixed-function hardware blocks with fixed functionality. They are not designed for flexibility or reuse between formats. They are designed for exactly 1 function and nothing else.

Even if AV1 and VP9 share structurally similar components, no VP9 decoder is going to work out of the box. It may mean that people who produce AV1-capable encoding/decoding hardware have a better starting point, though (provided they had VP9 hardware, beforehand)

Right but I guess I’m asking if they COULD be or if you’d need like a FPGA for that.

AFAIK a lot of "hardware" codecs are DSPs with some extra instructions that are good for video (like sum of absolute differences). In theory maybe they could support new algorithms with a firmware update. In reality, such firmware may simply not be developed or the DSP may not be fast enough to run a new codec.

Most DSPs I've worked with have an assortment of really specific extra instructions added for the particular application. I suspect these DSPs are similar - adding a new codec probably means adding a few more instructions, or even the odd hardware block dangling off the side.

Do you think the Mill family of processors could find a niche here? (if it ever sees the light of day, and I hope so because the technical videos are super-interesting (and educational))

[0] https://millcomputing.com/

People suggesting Mill as the solution to every problem without giving any reasons certainly doesn't give a good impression.

The Mill has been described as having more in common with a DSP than with a regular CPU. Apologies, I thought that was common knowledge.

There are. That's the reason we got instruction set extensions like simd.