There are already 'fish' adaptations that meet this description (so reptiles and amphibians need not be involved). They are just not all present in a single fish/shark species at the same time, or to the same extremes in the same fish species.
Here is a shark that can already "live" out of the water
Here is a fish that can REALLY last a long time out of water (though, admitedly not a 'shark' specifically)
This fish has legs (again, not a shark, but still...)
There have been evolutionary pressures to cause not just any fish, but sharks specifically, to be able to leave the water, at least temporarily. There have been evolutionary pressures for fish to last a long time out of water, and grow what are functionally (if not by definition) legs.
It's not a big leap to think a shark could combine these, along with increased size, and that would match the description very well, especially if the "arms and legs" description is taken no more literally than absolutely necessary.