To a degree, this is unavoidable, though it may primarily point to some DB tuning that would be beneficial.
The username search isn't an exact or a prefix match -- it a basic "contains" style check. Therefore, it will require MySQL to do a full table scan, so the time taken would be within MySQL. This is where InnoDB tuning and making sure that MySQL has sufficient memory (and CPU) to go through the results would help. Can you confirm whether that has been done?
There isn't likely to be much we can do here that doesn't involve more significant changes. There is a pagination check which gets the total number of results, and that does involve roughly doing the check a second time. In theory, we could avoid that if the result set is sufficiently small, though it doesn't apply if there's more than 1 page of results.
