There's a template for a fish, plus suggestions for how to modify it for various variaties, on page 58 of Mythic Locations. A dolphin and an octopus is included, but not a shark.
Lands of the Nile has stats for a "scorpion fish" (a 20 foot long horror with spines) on pg 97, with suggestions that they can also be used for a large shark. There's also the Heartbeast of Hilda Oddfish on page 14 of Mythic Locations, although that has been modified by the Mystery of the Epitome. I have a feeling there might be another set of shark statistics somewhere else as well, but I can't remember where.
Lands of the Nile and Between Sand and Sea between them have a fair number of animals you'd find in North Africa. Including giant snakes.
There are suggestions for modifying the Falcon template for different Birds of Prey in Lords of Men (pg 59). Lords of Men also have combat stats for different prey animals (but not full blocks of stats), along with stats for different types of hunting hounds, horses, a squirrel, magpie and monkey.
The Cradle and the Crescent has some stats for arabic birds of prey (pg 106).