Just to be clear: What I'm reporting here is a suspected regression.
The patch I linked, merged into coreutils in 2008, claims to fix the exact problem I'm having. The author measured time with `date` (see patch contents) which measures wall time. So I believe that the statement of the patch is that it improved `real` time from O(n²) to O(n). I observe that in the current version of rm, `real` time is O(n²). This is why I think this is a regression: The intended improvement of the patch is no longer in effect.
