The easiest way to bulk delete/restore is with your USB cable and a PC.
...
If I was seeing a Kindle slow down, the first thing I'd think is "maybe something got stuck indexing".
The indexer needs to work hard.
I have also (recently) heard mention that older devices (K4NT and earlier?) were less efficient at dealing with very large numbers of books, but all I can say is that I certainly haven't had to deal with that.