Be careful on what you delete in the All Messages mailbox in GMail. That mailbox shows messages no matter what mailbox they reside in in GMail (inbox, sent, etc.). GMail's default behavior is (or use to be when I had an account a few years ago) when you delete a message, it first goes to the Deleted Messages mailbox. Another delete of the same message would put it in the Trash mailbox. A third deletion of that message would delete it for good. Just remember that the All Mail folder will show that message in each of those mailboxes until it it removed for good.
You can change that behavior at the gmail website under settings. You can also choose to not show the All Mail folder in IMAP, which would keep it from showing in apple mail.
Here is one site that explains some settings that may help you:
http://www.macworld.com/article/2033842/make-mail-and-gmail-play-nice.html
You might also google this topic for other sites that may help.