Removing a folder can take more than 5 minutes if the folder contains a lot of jobs or subfolder and you have a large number of Jenkins user in your instance.

I did some test with a folder structure containing 100 items, going from 100 to 1000 users (using https://wiki.jenkins-ci.org/display/JENKINS/Mock+Security+Realm+Plugin) and the time needed to perform the deletion was duplicated

The problem seems to be located here, where for each item to delete iterate over all users in the instance.

The severity of the problem is greater or less depending on how users are provisioned (LDAP, Jenkins internal database,...)