The prelink package, as distributed via Debian unstable, does build on GNU/Hurd. After installing the satisfiable dependencies, use dpkg-buildpackage -b -uc -d to ignore SELinux and libc6-dev dependencies.

It is unclear whether it also does work. The testsuite (run manually) does FAIL on all tests, which is due to the prelinker doing something to the copied so that it faults on every invocation. This does not happen on GNU/Linux.

Not much in the prelinker is Linux-specific. src/get.c's is_ldso_soname should already cover our case (and what about At the end of src/arch-i386.c, .dynamic_linker has to be set properly. And, in that file there are some Linux process VM constants, of which REG2S and REG2E are the only relevant in the !exec_shield case. Probably these need to be adjusted. What else?