I've only fought him twice, but neither have I had a problem with him. I've found it effective enough to morph terra and blast him with spells, and use edgar's chainsaw, sabin's blitz, etc. Have shadow throw things at him as well.

I've also heard you can cast rasp on him, and when he reaches 0 MP from this, he croaks, but unless more than one person in your party can cast rasp (learned from Shiva), it is probably just as easy to pummel the crap out of him.

What level are you? I'm usually in the mid twenties by the time I reach him on the island.