I would say that you need to empty your trash more often. I know when I hit 10k files It took it quite some time to remove them. Also the amount of time it takes is no linear. It more of an exponal function
I don't have my time capsule plugged in. I don't think I need to stop it or repair permissions tbh... I just haven't emptied it in a while. I expected it to be quicker.