It's unlikely that they could walk across the ocean floor. It's muddy and there are all kinds of ravines and they'd be buffeted by the currents and so forth; and they wouldn't be able to see, so they'd need some magical sense of direction. Maybe they drift like seaweed until they hit land.
As to why they're not eaten by fish, perhaps the zombification process makes them unpalatable.