When I delete an email in Mail on my iPhone, it creates a new folder in Mail on my Mac called "Deleted Messages". Why is it doing this and not putting them in the Trash? I am using iCloud mail on both devices.
You can tell iOS which folder it should use for your deleted messages. Open up the Settings app and follow this path:
Mail, Contacts, Calendars < YOURACCOUNT (iCloud) < Account < Advanced (Mail) < Advanced
There you'll see Mailbox Behaviors options to tell iOS which folders to use for Drafts, Sent, and Deleted messages.
In your case, tap Deleted Mailbox and navigation your mail account's hierarchy to find your existing Trash folder. Select that and everything should work as you expect.
For syncing with iCloud you need to choose folder "Deleted Messages" on your iPhone to be default for the Deleted Mailbox. Otherwise it will create a new Folder on the server called TRASH and the emails you delete on your iPhone will in mail on your computer only be seen in this folder and not in the general Trash.