I haven't dealt with this problem for a while, but I'm sure it's getting large yet again.
In my case, I didn't care about retaining any backup history. So, here's what I did:
4 of the 7 tables that contain backup data do not have any foreign dependencies, so I simply truncated them. That runs instantaniously.
truncate table restorefilegroup
truncate table restorefile
truncate table backupfile
truncate table backupmediafamily
Then I delete data from the remaining 3 tables, in the correct order, with simple delete statements.
1. delete from restorehistory where restore_date < '1/1/50'
2. delete From backupset where backup_set_id < 200000000
3. delete from backupmediaset where media_set_id < 200000000
You may want to only delete a quater of the above tables at a time. It's important to have the where clauses there, even if they specify all the data in the table. For some reason, it's much, much faster than a delete without a where clause. (I'm guessing it's because SQL doesn't have to scan the table to determine dependencies in other tables.)
You could make this faster with a little more investigation. You could remove the dependencies, truncate these tables, then put the dependencies back on. You might also be able to tell SQL not to write to the transaction log with doing the deletes.
Note, only do this if you want to drop ALL history and restore data. I did this because I had so much data. I'm log shipping multiple DB's on a per minute basis.