Are you sure it is freezing? Or is it merely taking a long time to finish? Check the spinning progress indicator and the orange hard drive activity light on the front of your PS3.
Try going into Safe Mode and using the Restore File System option to check for errors. Afterwards, delete all the corrupted data it finds.
Make sure you have regular backups of your save data that you don't want to lose. You can make manual backups with a spare USB thumb drive and Saved Data Utility.
Cool, thanks for the advice. The little progress timer in the right hand corner of the screen was in fact moving so it was strange how long it took. Ill try safe mode and see if that helps. im off to the store this week to by a memory card or an extra HD to store all my games on. I should have never bought the 40G PS3...not enough room.
Yes, some of the game data is really large and takes a very long time to delete. Some of them are more complex than others, so file sizes aren't a perfect estimate of how long it takes to delete them.
You will need to swap out the hard drive inside your PS3 if you want additional storage for games. External hard drives or memory cards only store backups and your personal music, videos and photos.