Microsoft provides “sp_delete_backuphistory ‘6/1/2011’“. However, this can take a very long time unless you also add indexes to the backup table. This is what did the trick for me:
Create Nonclustered index idx_backupset_finishdate ON backupset (backup_finish_date) INCLUDE (backup_set_id, media_set_id)
What was taking 20 minutes now takes 1 minute.