This turned out to be an issue with OSX 12+ ad-hoc signing anything compiled on it with a machine-specific signature. This made codesign fail with no useful message. Trying this on OSX11 gave a useful message about Mach-O header segment overlaps. In the end, the solution was to remove the ad-hoc signing with something like optool which made it possible to correctly sign.

Just to be clear, I have the same issues with Xcode 12 and 13 and so it seems to be OSX 12 related.