Gmail doesn't have folders. All your messages are saved in All Mail. Everything else (Inbox, Starred, Drafts, user-labels, etc) are just "views" into a subset of the messages in All Mail. And since there's only one copy of any message, if you delete it from any label, you're deleting the only copy, so it's gone from all of them. If you delete a label you remove that "view", but the messages are still in All Mail.