Partially Amphibious (Ex): A mastodonsaurus can survive for a number of rounds equal to x times its Constitution score out of water. After that, it risks drowning. For a typical mastodonsaurus, this is x rounds, or x minutes.
Edit: On second thought, should we just adapt this?
Water Dependent (Ex): Sahuagin can survive out of the water for 1 hour per 2 points of Constitution (after that, refer to the drowning rules on page 304 of the Dungeon Master’s Guide).
CR 4?
Advancement: 6-9 HD (Large), 11-15 HD (Huge)?
A mastodonsaurus is 12 to 15 feet long, weighing around x pounds.
Bonus to saves vs. temperature extremes is good. I think we should ditch improved grab and swallow whole, and the Hide bonus in water. They appear to have been predominately terrestrial--we might not even want them to get a swim speed.