I am successfully using Eclipse Helios with the AVR Eclipse plugin.
The Arduino Mega uses an ATmega1280 microcontroller at 16MHz, so make sure you choose that when configuring your project.
To upload to the Arduino Mega, you need to go to Windows, Preferences, AVR, AVRDude, Programmer Configurations, Add.
Then select "Arduino" from Programmer Hardware, set the port to the serial port your Arduino shows up as (under Windows, you can find this by going to the device manager). Set the baud rate to 57600 and leave the other parameters alone.
Now go to your project, properties, AVR, AVRDude, and choose the programmer configuration you just created from the list.
You should now be able to upload to the board. Compile your project, then make sure that the project is selected in Project Explorer (typically the leftmost panel). Right click on the project, then select AVR, Upload to board (you can add this as a toolbar button too) to upload.
If you get STK500 protocol errors, it's possible the timeout on resetting the board is not appropriate for you. Experiment by manually resetting the board and hitting the upload button.
I hope this helps.
PS. You may be interested in MHVlib, a runtime library for AVRs, developed in Eclipse. You can grab the Eclipse project from http://www.makehackvoid.com/group-projects/mhvlib-efficiency-oriented-library-avr-microcontrollers