Go through your pm's and delete the ones that you don't need. Then once you have deleted all of the ones you don't need, go to the 'Trash Can' and make sure to delete any pm's there because they will take up space if you don't delete them.
I have to do this every once in a while, but it feels good when you get it down to a handful of pm's.