Motor controller

I have an underwater scooter Cuda 650.... http://www.dive-xtras.com/pages/products/cuda650.asp
that uses a BFA42-2d-200 motor http://www.magmotor.com/brushless/bfa-ba42.pdf
Battery pack is a 34 serial 14 ah NiMh pack (41v nominal)

What is involved in making a new contoller for it based on Arduino?

As it is the controler has a 7 speed contol. It starts off in 3rd and a double click on the triger will increase speed while a single click will decrease speed.

What I would like to see is perhaps a change in speed options, a soft start, low battery warning and speed memory. These dont seem too difficult to implement being PWM, and voltage reading functions. But I have no idea on whats involved in running these types of higher voltage motors.

I think you need a stepper motor library to handle the stepper's speed. Recently I am working on a project that handle four stepper motor. The AccelStepper library works just perfectly. You can control the motor through it not only to set the specified speed, but also the "acceleration" and "deacceleration".
But the hardware side I can not much to say.

Those are not stepper motors!

A 3-phase bridge is needed to drive such hall-sensor brushless motors - not an easy thing to get right at those power levels I'm afraid, I suspect the motors involved (the precise model is not in that datasheet, BTW) have windings of about 0.02 ohms resistance - stall currents limited only by the battery pack in practice.

The datasheet implies there are severa options for those motors (encoders, hall sensor, etc) that are not described by the part number alone.

A photo of the existing motor and controller would be very useful (and any part numbers for the controller - its specs may be available for instance).

You may find http://ww1.microchip.com/downloads/en/appnotes/00857a.pdf useful. It's illustrated using a PIC microcontroller, but could be adapted to use an Atmel mcu instead.