Another thing I noticed, TheAvatar said it was high current? Mah is not a current rating
I wasn't talking about capacity! I was talking about (I=P/V) (650mA=3.9W/6V) 650mA... (which is a very high current demand for a series of AA cells (paralell would obviously make things easier). Look at what James' example: "1000mAh battery can't do 2000mA for 1/2 hour." In an ideal system you could, but James is 100% right and batteries are limited in their abilities. Also, always be suspicious of tech data sheets. These are guides, not exact real world performance.
Check what the orginal official battery pack was... NiCd, NiMH, or Li-Ion? Unless the origianl manufacture's pack was NiMH, I wouldn't try to use NiMH AA cells.
This is a very high current application. I think NiCd is really the only suitable rechargable battery for this application... unless you find some Li-ion or Li-polymer batteries. NiMH will probably work, but not nearly as well. NiCd handle high current very well. It is one of the few things they do well (that and lower temperature applications).
Sure NiCd have 2/3 the power density of NiMh and will last for 75% of the charge cycles that NiMh will, but NiCd are cheap. You can probably buy 10-16 NiCd for the price of 5 NiMh. There is no way you should be running the NiCd totally dead on one dive if you have good ones. The NiCd should last 1.5-2.5 hours. NiCd recharge extremely fast. The first set should be recharged by the time you come up from your next dive, assuming they don't finish recharging between the end of your first and the start of your second dive.
If you are using a nonrechargable battery, use a lithium battery, not a standard alkaline. Lithiums handle the high current applications a lot better.
I would not solder directly to a battery unless I knew exactly what I was doing. You could ruin the battery, or if you are stupid about it, cause it to leak. Solder all wire connections, but the batteries should be made to connect via pressure (springs... like every single electronic device out there).
Just in case you somehow forgot,
YOU WILL NEED NOT 4, BUT 5 1.2V CELLS CONNECTED IN SERIES IF YOU NEED TO MAKE A 6V BATTERY!