Whatever the tagging of the connection, I do feel like it is possible and appropriate to use a linear way that approximates the centerline of the area that might be traveled.
Take for example, a route along a curved bay like this example from the South Coast Route linked in the original post:
Even if a “precise” placement on the beach is impossible to determine, a rough estimate is going to allow routers to be less wrong in determining distance to be traveled than simply a relation identifying the two end-points that are always above water.
I do think it makes sense to tag such a connecting way differently than paths that can be seen on the ground, but I have not formulated a strong opinion as to whether this should be a new highway=* value or a separate tag used on highway=footway|path|etc.