When you move a folder to the Trash, your computer just moves the folder to *original location*/.Trashes/Folder
When you empty the bin, your computer needs to go through the directory and remove the entries for every file. Your backup is going to have entries for every backup, so it will take awhile... upwards of 1 million file entries in some cases.
You can either wait for it to finish, or format the drive. (Warning: formatting the drive will delete everything on the drive.)