I finally managed to upload my first underwater video.
Color editing was done in Cinelerra, since Kdenlive doesn't have a good white balance feature.
All the other editing was done in Kdenlive.
The title effect at the beginning of the video is a combined green/blue screen.
I created a green background with a blue strip with a white borderline in Inkscape.
Then I used a blue screen effect to replace the strip with the some wave shots and rendered it to a separate file.
In the second run the green was then replaced with the final scene. (With some added transparency)
Render profile was a modified h264 4Mbit video bit rate and 256kbit AAC audio bitrate at 44.1kHz samplerate.
(128kbit is really too low if you want to have decent audio quality)