I guess this could be it:
Maybe Chrome and FF already split cookies headers into different fields, as per the suggestion in the RFC, and Edge doesn’t.
Since haproxy does not implement the necessary concatenation, and your backend probably is unable to handle it, it doesn’t see the cookies, therefor rewriting them at every transaction, leading to this behavior.
Capture and Analyze the cleartext HTTP traffic between haproxy and your backend; if Chrome and FF requests have multiple “Cookie:” lines in the HTTP/1.1 cleartext traffic towards the backend and Edge has not, than this could be it: