Interesting to learn of the US rule. In the UK, up to £8000 of relocation expenses can be provided tax-free, for "qualifying expenses" (mainly costs of buying/selling home and moving -https://www.gov.uk/expenses-and-benefits-relocation/whats-ex...) although there is some allowance for a flat-rate payment if it is reasonable (https://www.gov.uk/hmrc-internal-manuals/employment-income-m...). I'm reasonably confident any payment would be tax-deductible for the employer, it's just a question of how much is taxable as income in the hands of the employee.
It used to be that way that any amount (I think?) was considered tax exempt/tax-free if it was used for the purposes of a qualifying list of expenses (similar to what you have in the UK). There was a tax law passed that came into effect in 2018 that removed that rule, however. I believe it'll go back to 'normal' in 2025 for moving expenses.