Performance impact during texture layer loading
From the way the problem only manifests when you start overwriting previously used texture tiles, I suspect you're running afoul of some driver heuristic that's attempting to manage the lifetime of the texture data on the GPU.

In general, when you update buffer or texture data from the CPU, the driver has to make sure it doesn't overwrite anything that might still be in use by the GPU (considering that the CPU and GPU run asynchronously to each other). There are various ways the driver can do this, such as internally double-buffering the texture, inserting sync points (for the CPU to wait on the GPU), or initially copying data to a temporary staging buffer and then later re-copying it to its final destination. All this stuff is under-the-hood and the driver makes its own decisions about what strategy to employ in any given situation, using some heuristics based on texture size, usage patterns, etc.

I can only guess at the details, but I suspect what's happening is that the driver is getting into a state where it thinks those previously-used texture tiles are still in use on the GPU somehow. Then when you start to overwrite them, it decides that it needs to make a second instance of the whole texture, and laboriously copies everything over before finally doing the updates you wanted—or something like that. That could be the many tiny draws you see in Nsight.

It's still a mystery why it's taking tens of milliseconds to do that, though. Maybe the textures are large enough that a second copy of them causes you to run out of VRAM? In that case, you'd get a lot of thrashing as things are spilled to main RAM. That's just a guess, though. As for why the bad behavior only happens for a few tiles and then goes back to normal, it could be that the driver heuristics are deciding to switch to a different strategy at that point.

Anyway, as for how to fix it, you might try using glInvalidateTexSubImage whenever you free a texture tile. This lets the driver know that you don't care what was in that texture tile before, which hopefully will convince it to just update the texture in-place rather than doing anything crazy with it.

Another thing to try is to make sure you don't try to re-use a texture tile in the very next frame after you free it, but give it a frame or two of "downtime" before re-using it. But it sounds like that's probably the case already, given that you prefer unused tiles before you start re-using them.

If that doesn't help, I'd recommend sending an email to devsupport@nvidia.com. The OpenGL driver team there can likely take your Nsight captures and help diagnose the issue, and fix it if it's due to a driver bug.