This is easily solved by looking at the direction of waterways. You start at the point where the river touches the coastline, and you go up the graph. Each connected way should have a direction towards the coastline. The moment a way is directed the other way, the watershed stops.
So in the illustration below, we start with the node 1 because it’s a waterway=river and a natural=coastline meeting in a node. We go up (down) the graph:
1←2←3←4
and all the nodes are connected so that the direction is towards the previous one. They are all in the same watershed.
But then we get to 6←7 →9, and 9 is directing away from the previous one, so the watershed stops there, the waterway 7-9 isn’t a part of this watershed. We can include canals, pipelines, anything, direction shows where the water is going.
-------------1-----coastline-------
↑
2
↗ ↖
3 6
↗ ↖ ↖
4 5 7
↗ ↘
8 9
This is what I’m trying to represent. Mark the direction of the stream from 7-9:
The problem is, I don’t know how feasible it is to do this in the existing code base, and for the algorithm to be reasonably fast for the whole world.