I reckon you have an exostosis (a benign bony growth projecting outward from a bone surface) on your heel bones, around your Achilles tendon's insertion. This rubs against the 'heel' of the shoe, which often contains cardboard-like material around the heel to support it.
I haven't had this problem myself with any of my shoes in the last ~5 years without resorting to my more nefarious solution. In your case I suspect the heel bone rubs against the 'heel' of the shoe, because there's too much room (either due to your foot type or poor fit) or your laces aren't tied properly. When the shoe fits your foot like a glove, they can't move relative to each other and thus you won't get the damage on the shoe & blisters on your heel. Making the shoe fit better can be done with insoles/orthotics, but obviously you'd prefer to buy shoes that are a better fit in the first place. I'll ask around to get some advice on how to find a good fitting shoe (not based solely on 'it felt good').
If you can't find a shoe with a better fit, you could cut out part of the material. It involves opening up the stitching at the top of the 'heel', then poking in between and removing some of the support material. However, this also means the heel of the shoe will no longer be able to give the support it was designed for and you'll have to be able to stitch (or glue) the shoe back up. On the other hand, you have first hand experience with the damage your feet will do to the shoe if you don't, so it might be the lesser evil.
Disclaimer: my father makes orthopedic shoes, so if I need it, I let him do it for me :-)