It doesn't have to be something that everybody can do on a regular basis, all it takes is one male and one female, once, over a period of 200 thousand years.
Plus, we know little about the ability of Neanderthals to swim, or their water requirements.
And there are plenty of sources of water besides straight up water, as I'm sure you know. Any land based lifeforms you can eat or chew on may contain fresh water. Even fish from saltwater contains plenty of freshwater in its meat.
And of course, they could've carried food or water during the trip.
The world record is 225km swim over 50hs. So it's reasonable to think that 100km could be achieved in well under 24hs. 100km gets you from mainland to crete.