I have several email accounts. I have a Gmail account, an iCloud account, and a Yahoo account, and each one has a Trash folder. At the top of my mailbox list there is another Trash mailbox right along with Inbox, Sent, Draft and Junk (if you don’t see a Draft or Junk mailbox, don’t worry about it; they get created by Mail when needed). When I delete a message from one account, the thought is that it should go directly into the Trash mailbox at the top. It might do that, and it might also wind up in the Trash mailbox that is directly associated with the account. If you delete messages on your iPhone or iPad, this is usually where the deleted message goes.
You do have to manually delete the messages from the Trash mailbox that you have in each of your email accounts. Simply highlight the message(s) and click on the trash can icon in the toolbar - just like any other message that you want to delete. When you delete a message from one of those Trash mailboxes, they go immediately into the top level Trash mailbox. Uh, oh! So now you have to empty the top level mailbox.
To empty the top level Trash mailbox requires a different method. If you right-click on ANY mailbox, then a pop-up menu appears, and in that menu you will find, “Erase Deleted Items…”. If you click on that menu item, then another pop-up dialog box asks, "Are you sure you want to erase deleted items in the selected mailboxes and in the Trash mailbox?” Of course you are, so click on the Erase button and it will be emptied. If you attempt to delete any message from this Trash mailbox using any other method, sometimes nothing happens. That’s because the message is flagged as deleted and shows right back up in this Trash mailbox.
If you have thousands of messages that you want to delete, it might take a while. What happens here is that Mail sends a message to your server (the one that is handling your email account) to delete those messages from the server. The server sends back a confirmation - or an error message. If it is a confirmation, nothing happens. If it is an error message, which I sometimes get on my iPhone, it usually says something like the server was unable to move the message. Don’t worry about that error message; somehow things get straightened out eventually.
On your iPhone in the Mailboxes screen (top level) you will see an “All Trash” mailbox. Tapping on that mailbox shows you ALL the messages that have deleted while using Mail on your iPhone. Tap on the Edit option in the top right and you will then see at the bottom right “Delete All”. Tapping on that option will show another pop-up to choose either “Delete All” in red or “Cancel” in blue. Emptying your deleted messages in this way will delete them from each of the other email account Trash mailboxes on your iPhone. I have not yet seen this “All Trash” option on my iPad.
On my iPad, to empty the trash I have to go to each email account, find the Trash mailbox there, tap on the Edit option, then tap on “Delete All”, and finally tap on “Delete All” again. There is no option at that point to Cancel.
Now the confusing part for some is that you will find two Trash mailboxes associated with each of your email accounts. One is up with Inbox, Sent, etc., and it has a normal trashcan icon, and another is found in alphabetical order looking like any ordinary mailbox with a folder icon. For my iCloud account, that second trash mailbox is labelled “Deleted Items.” Do not worry about those secondary Trash mailboxes. Their contents get emptied when you empty the top level Trash mailbox.
One would think that if you empty the trash on the Mac that it would also empty the trash on the iPhone and iPad. Unfortunately, this is not the case. Even after diligently emptying the Trash mailboxes on my Mac, I still find contents in the Trash mailboxes on both my iPhone and iPad.
I may have missed some detail or gotten something wrong, and if so, please let me know. I hope this helps.