That is Google's Data Mine that it uses to make money off of your information.
You need to remove it from IMAP on the Gmail Settings web interface. But that doesn't delete the email stored on Googles network.
Gmail doesn't use folders, it uses Labels. A message can have multiple labels. Initially, a message has an Inbox label and an "All Mail" label. When you move it out of the inbox, like to delete it, it only removes the Inbox label. The All Mail label remains.
This article, among many others, describes how to get Gmail's non-standard implementation to work with Mail.
http://jeffschuette.com/2012/03/07/setting-up-apple-mail-to-rock-and-roll-with-g mail/