How can I free storage used by Mail on iPhone?

The mail app does not contain your mail; it displays mail in the mail database. So deleting the mail app and its data only deletes its settings, not the actual mail. It works this way in case you want to use a different mail app that the built in one. To delete mail content you must delete the mail database. To do that go to Settings/Mail/Accounts, tap on a mail account and delete it. If the mail account is iCloud you can’t actually delete it, but you can select and delete the messages in the mail app. But any other email account can be deleted to remove its content.