Do you think this is related (another symptom of) #41940 ? It too is about amphibious movement, and seems to happen only with rulesets and branches that have "Coast" ships.
Seems to me, it's yet another bug in a close code region. The problem here happens because the fueled unit tries to target either the destination tile or next refuel point on the way to it and the map it uses in finding this fueled path is not "overlap" (as supposed by the code using it) but needs actual arrival.
I look at the code of dai_unit_goto_constrained() and see that we find the path to another tile at least twice, once for goto_is_sane() and once for real pf_map_path(), and the two pathfinders potentially differ only in handling unseen empty cities (why?). And for fueled units even once more before, in immediate_destination(). And if we decide to go somewhere, it's very probable we have traced a path there before. Looks like some cleanup needed...
I am almost sure that we can clear immediate_destination() from both places in the code where it is used without changing any behaviour except this bug. It's probably just a relic of the times when the fuel pathfinder was young and clumsy.
Removed that one occurrency of immediate_destination(), the other one affects carrier movement (probably, in a foolish way though) and should be dealed separately.
Spotted in master but smells like affects prior versions. Look at theCeltic trireme at (32,27): It wants to load a caravan from (35,28) and by the idea should go adjacent to it, but it tries to "fly" to the tile itself but actually it has no wings so we get the message "Did not find an air-route for Celtic Trireme365 (32,27)->(35,28)", and the pair gets stuck for many turns.