Why didn't it work? Was try 2 ionice?
Now the second interview question: how did trickle-rm work? How can you simply "reflect" the back pressure of the "x rm's per second" constraint back onto the "walk the directory tree to find the rm's to do" so that the tree walk generates a trickle of i/o operations?
I'm surprised that rm's io would cause that much of an issue. I thought it only removed entries from the partition table.