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.