On my first playthrough, it took about 6.5 hours and 8 stages.
I started the battle with my guys at level 70 and knocked first 10 bars off (left few time while doing that). After that, left to level my guys up to 99. Then I came back to continue the battle from there. I had to leave more often when I got to the last 10 bars.

I just beat him on my 122333 (aka low-level) challenge, and it took around 14 hours and 7 stages.
The only reasons I left were if I ran out of Ethers & Phoenix Downs or if I had to go do something.