I ran into this issue recently when introducing another MTP device after not having any problems with a couple of other devices. I hadn't spent any time troubleshooting this as the added device was for occasional use only but this thread (and there have been others before it) prompted me to have a quick look. The situation was:
Existing devices:
Android 7, thousands of books on 32GB microSD, USB-3 - no problem
Android 8, thousands of books on 64GB microSD, USB-C - no problem
Added device:
Android 7,
2 only books on 128GB microSD, USB-3 -
took 3 or more minutes to scan every time it was connected with Calibre.
In all cases the books were in one folder in card's root with subfolders under that for each primary Calibre Tag (the books had only one such tag each), Calibre was given only that folder and its subfolders to scan. All else, such as the Save Template and Automatic Metadata Management (I think that is also the default??) was equal.
What I have found with the problematic device is that with it connected and the lengthy scan finished, then doing a manual metadata cache update (Calibre menu "Device>Update cached metadata on device") the problem has now gone away for future connection instances.
This seems to have survived system reboots with the added device now scanned quickly. If the problem with the added device was typical of the issues others have then there are some clues here relating to where the cause may lie (and hence my lengthy explanation
).