The answer that I think is the most likely is on Wikipedia, which is that the term derives from maybe as far back as the Tokugawa era, where there was overlap between bath houses and the sex trade. The water in the bath houses became a euphemistic reference for the sex trade.
However, I noted that the reference cited on the Wikipedia page for that explanation linked to a text by Boye De Mente, who is far from a reliable source of information about Japan. So a more believable reference would be advised if you need something truly authorative.
On that same page, they also have references to possible origins from Japanese phrases that link water to aspects of the sex trade:
勝負{しょうぶ}は水物{みずもの}だ ("Gain or loss is a matter of chance"). The idea here is that the entertainment industry (which extends to the sex trade) is fickle, and success comes and goes like the flowing of water.泥水{どろみず}稼業{かぎょう} ("muddy water earning business"), a term for illicit business水茶屋{みずちゃや} ("public teahouse"), which seems to imply that at some point in Japanese history you could probably find your way to the sex trade by going into certain teahouses.
I think the origins in these phrases are a little bit overthought, but then what do I know? Maybe they're true.
In any case, it seems like the true origin isn't known for sure, but hopefully these will be helpful for you.
