This rotation problem we are going to solve in Track View. Open it.
When Track View opens to make thing easier right click on first button and select Animated Tracks Only. This means that only animated object's tracks will appear. Now right click on World and select Expand Tracks. If the Main bone is selected its name will apart bordered with yellow. Find its rotation line. Keys are those eggs like dots. Selected key is white. Use move tool and select and move rotation key from the frame 0 to the frame 78. Now the rotation will start at frame 78 and will and at 90. Turn of Track View and play animation. See?, already better.
So far we have main movement. Its time to add small tail and head movements to add realism. Only bones we are going to animate are: Main bone, Pre-tail bone and Tail bone. Lets start with the tail animation. So how many times should tail move form left to right? Lets say that one movement is 2/3 of a second. We have 100 frames of a little bit more then 3 seconds. That means that movement will last 20 frames.
So go to the frame 20. Turn on Animation button. Select Pre-tail bone. Use rotating tool and rotate it so it look like a picture on the left. Rotate the bone in Local coordinates and looking it from the top.
Now do the same with the Tail bone. See how the mash is not smooth at the place where the bones rotate. This is not a big deformation and will not affect how animation looks so will leave it for another time. But if you have to do something under Skin modifier/Gizmos you can use Join Angle Deformer. This sort of envelope will deform skin (mesh) as you wont.
Try not to animate Main bone for now. You will do this bone at the end. Try to do the tail all the way and then play animation to see how it looks. Then add a Main bone animation and see how it look then.. You will see the big difference in shark movement. Movement is more convincing.
Go to the frame 40, turn on Animation button and rotate Pre-tail bone and tail bone like at frame 20 but on other side.. and do like this two more times (frame 80). After frame 80 do same tail movements but on every 10th frame because we want to shark go faster when its going away from the camera like it angry or something.
And at the end I added a Target Direction light with Noise as a Projector map. Look like under water. Background is white and Animation is rendred with Brazil r/s. Click on image below to see the animation... done in divx.