Gmail – All Mail; deleting from disappeared the folder items as well!

See this Google article : "Migrate to Gmail from Hotmail, Yahoo Mail, AOL Mail".
This describes utilities that Google had developed for fetching mail and contacts.

You will first need to separate the messages that you want to keep from those you want to delete.

I'm not sure I understood the question entirely, but there are a few methods to do this:

• Use a search query to filter on those that you want to keep (e.g. label:list from:me), then either use this query negated in the next step, or star/label these messages.
• Go through the 60K+ messages manually. As you do so, you should either star them or add them to a label.
• Search for messages that you know you want to keep based on keywords and manually mark them with a star or label. As you do this, you should negate those that have already been selected to keep the list small. So for example, if you know that a message you want to keep has the words "save this", you would run "save this" -is:starred, then select the messages and star them.
• You might already have the messages in a specific label, in which case you are ready for the next step.

Now you can simply run a query to select all those messages you want to delete and subtract those that you want to keep. Simply run a query such as: label:list -is:starred. Next, select all the messages in the list (you will need to tell Gmail to select all messages not just the first 20 by clicking the link above the list of messages). Once all of them are selected, you can simply delete them.

In case you want to use a label instead of stars, simply use -label:foo instead of -is:starred in your query.