The manual page for the deletion records is:
Administering HCP > HCP services > Garbage collection service > Configuring the garbage collection service
Note that "deletion records" refers to the transaction log where this information is kept, not the actual objects themselves.
Suggestions:
1. Try to remove the folder/s using the namespace browser or curl to rule out any caching issues with HCP-DM
2. If the above does NOT return an error then run GC again and then try to delete the namespace.
3. If this doesn't help -- open a case with Support.