I'm not sure exactly how new this is, but I've just noticed when you press the select all link in Gmail/Googlemail, a new option appears which says 'select all X conversations in "label"'. This is great. Now you can delete all the messages under a given label without having to delete those items a page at a time.