Deleted Messages seems to be there only if you choose a server stored IMAP folder.
If instead, you set up Mail settings under your account in the Advanced tab to "On My iPhone: Trash" rather than "On the Server: Deleted Messages" your deleted emails should go directly to the trash.