Today I added stamina and lap counting (for the player, no AIs yet). Yay!
Also, maybe you should play a different sound track for whether you are moving or not.
Perhaps, though with background music in place the sound effects will be less prominent.
http://www.wanilla.net/random/undersea2/index2.html
Please excuse the hard-to-readness of the HUD while not in full-screen, and the strange aspect ratio while in full-screen. I’m working on preparing a system that allows players to choose their aspect ratio before entering full-screen mode. Other than that, you’ve got a title screen and a fairly well functioning race against an AI turtle. Have fun!
Notes:
AI turtle won’t ever surface for air before being completely strangled yet. He slows down after a time to preserve stamina, but as there’s no way yet to recover stamina without outright stopping, he never does that either without being forced. You will likely learn his patterns and beat him without a hitch. I’m working on this.
Also, there are nice interface elements notifying you when you run out of oxygen, stamina, or both.
Big updates here!
First off, game mechanic simplified for the player: There is no longer stamina, nor will there ever be schools of fish for your consumption.
Secondly, I’ve added a clam who will periodically generate a pearl. Grabbing the pearl will result in a short speed boost, thus adding incentive to go to the bottom, away from the safety of fresh air.
Lastly, I’ve added a mechanic where the less oxygen you have the faster you swim, as an incentive for the player to hold off on getting air often.
The AI has been improved, and will now dive and surface appropriately so as not to drown.
One thing I noticed is that you can get serious hang-time by holding down shift and space and diving up to the surface. I was able to make it clear out of the water and onto the surrounding land. It does feel great though to make your turtle leap so high.
I know, I’ve noticed that too. I’m not sure what to do about that, other than put up invisible walls or design the levels better. 
I could always crank the gravity up a bit.