If I may ask a dumb question, were you searching above or below water? Reading the quest dialogue, they specifically mention you're going underwater to come up at the inside of a well and she is in a tunnel that's beneath the surface, so you could walk on the same spot and be on land as opposed to where she is, some distance beneath you.