Are your songs maybe stored on some external storage? That kind of setups have proved to be problematic because (depending on many things) they may require transferring the whole files between your file server and the Nextcloud server to be able to index them. But still, the process should not slow down as it progresses.
Which database system are you using? If you were using SQLite, then it could explain the problem, as it is not suitable for anything but toy-installations.
As a reference for which kind of performance you should be getting, my test environment is RaspberryPi 3 with internal storage of Nextcloud located on an HDD attached with USB 2. It’s fair to say this is a low-end server. But still, I have managed to scan 60000+ tracks library within a reasonable time. The scanning pace is pretty much constant and about 10 songs every 3-4 seconds.