If I remember correctly, the initial sound was recorded on a zoom H4. I positioned it outside and very close to the edge of a full bathtub, submerged my head slightly underwater, and then made a roaring sound. I actually don't recommend doing this, it was harder to roar with my face in water than I thought it would be.
For some of my "Sharktopus" sounds (which you can find under the cmusounddesign account), I also recorded my cat mewing for dinner as my base sound...this one might be that as well. The Sharktopus gnawing on bones sound was my cat eating dinner.
In any case, from there I time stretched it a little bit without any correction to give it the inhuman quality, and then applied a high shelf eq to cut out high frequencies to make it sound further like the sound was traveling through water.