Identification time has two components: constant and linear. When database size grows from 500 to 3000, only linear component grows 6x, the constant component stays the same. That's why the total increase of identification time is only 2x.
Our identification algorithm performs full exhaustive database scan. We don't use any internal template indexes. No single template is skipped. The nonlinear identification time curve is caused by the above mentioned constant overhead.
Another issue affecting identification time is the recently introduced automatic selection of identification speed. For smaller databases, lower speed setting is selected in order to improve accuracy where high speed identification isn't necessary. You can force particular identification speed by altering the appropriate parameter (IDKit.IdentificationSpeed in .NET or CFG_IDENTIFICATION_SPEED in C++).