One of the key quality that hyperloglog relies on is that the action of hash distributes any input to any output with equal probability (eg. any input have 1/m chance to be in a particular point in output space where m is the cardinality of the output space)
I can't seem to prove this rigorously, am I understanding the paper correclty?
I think it's more a practical concern than something that can be proven conclusively; the behavior characteristics (e.g., collision probability) are known for a given hash function, and if you're implementing HLL, you choose an appropriate one based on your use case (expected cardinality, etc.)
Redis uses a modified 64-bit MurmurHash2, for example.