Try adding the new folder by going to your email's website instead. It should show up and be usable on the iPad.
This.
Some mail servers won't allow this feature and some will. My Work Exchange email I cannot create a new folder, but in Gmail I can.