Technically, this depends on the filesystem and the structure that's been set up for it. But in the normal case of UFS/EXT, the system has to visit each individual file to release space. In the case where you have many small files, it can take quite a while to walk the directory to release space.
Because your usage is as a backup, you might consider changing the layout before you need the space back. One option is to take the directory (potentially with many small files) and tar or zip it up. This will take some time, but can be done any time after the backup. When you have the archive file in place, delete the directory. At the end of the process, you have a single file on the filesystem, and can still pull any data you need from it.
When it's time to remove, you can
rm a single file, which will go much more quickly.