Fixed it.
Looks like it was caused by my Hotmail account which is linked to my Gmail, leaving 11000 unread messages in Gmail.
I setup my gmail in Outlook, downloaded all the headers (still took over an hour!), then marked all as read and synched with the Imap folder.
Then I removed the Gmail account from my iPad and re-set it up. Strangely, the iPad remembered previous settings and still said I had unread mail, so I removed it again, did a hard reset and set it up yet again.
All seems fine now.😀