Thanks for the info.  Here is what I surmise from the data.  

* The shape of the curve matches the expected memory latency curve for random memory accesses for a given working set size.  The graph of your measurements looks similar in shape to this one:  https://www.extremetech.com/wp-content/uploads/2014/08/latency.png

*  The last line of the measurements has N=1,500,000,000.   That would give an approx 70GB setobject that refers to another 100Gb (or more) of strings.  Unless you are working with an extraordinary machine, most of that data will have been swapped to disk.

* Dividing the 1,500,000,000 elements by the time of 25,068 seconds gives about 60,000 deletions per second.  This number coincides nicely with the random access performance of a typical SSD rated at  50,000 IOPs.

If this reasoning is sound, all it proves is that random accesses to virtual memory are limited by the speed of the hardware for that virtual memory.