[stumped]

With over 4000 books u are probably pushing the boundary of what that device is capable of .

Unless you have the 32gb version, which Harry t has squeezed 8000 onto.

you could maybe check free storage via a pc connection. If it is running out of space that may explain the slowdown
Even with indexing disabled it may have to add to various lists and databases before the book shows up.
Ps I did not know you could disable indexing ?

A simple test to rule out calibre being the slow down cause would be to add a book directly with windows tools via usb, just by copying to the correct folder, and see if it still takes the same time to appear