Also I bet these systems have lots of little moving parts under the surface no one really considers, but these little parts prevent an upgrade.
Payroll is highly regionalized problem - every state and city has different rules/taxes and very unique ones as well. Its often not so simple to generically describe a payroll tax and plug in different configs per region. Much hidden complexity that's grown organically over time as laws/taxes change (which they do!).
A rewrite would be an archaeological dig. I would have to be paid a lot to take that problem on.
It's also not trivial software to manage, so often it's outsourced as a service (run by humans) on top of software that cut the checks for your employees. Makes me think that the margins are low? I dunno.
Modern companies like gusto are changing this