Hi Robb,
Firstly, I believe that it’s important to remark that the MAG3110 is not a hall sensor.
And also I’m thinking that you should be concerned about saturating the full scale range (FSR) of the device because it is not a very big scale (+/-1000uT).
It is hard to answer your question regarding this because we have no idea how strong the fields get in your application. I am seeing that typical magnetic field strength for Melexis part is 50mT which is 50x the FSR of MAG3110. So, according to my point of view according to the information you have sent, I believe that saturation is possible, but you may be able to get around this by using a weaker magnet or moving it away from the sensor.
Once the saturation problem is solved, in theory, it is possible to calculate the magnetic vector that is coplanar to the sensor top surface using only the x and y axes of MAG3110. If you want less 1 deg of accuracy you will probably need to do perform the hard/soft iron calibration. And even using this calibration I cannot warranty that you can achieve this since this will depend on many other different factors.
You can probably want to take a look at our FXOS8700 instead. It has slightly higher FSR and better temperature performance: http://cache.freescale.com/files/sensors/doc/data_sheet/FXOS8700CQ.pdf