Try not to use active record on search with that many records, rather use getPdo().
Index any column you expect to search.
Do not use star if you don't need all fields, use only the fields needed.:
SELECT * from ... /// Don't do this
// instead
SELECT `id`, `mydate', (and only fields needed) from ...
In a search text box use more characters, example you are finding someone with the last name of White.
Don't enter just a w.
Enter at least or 4 characters like whit.
If a search can be done via a numeric index, use it instead when possible.
I.e., You need to pull up Joe White in the database. However if he has a customer number, use it.
Numeric is always more efficient.
GetPdo() example: https://laracasts.com/discuss/channels/guides/getpdo-usage
Bind your parameters.
And:
https://laracasts.com/discuss/channels/guides/length-aware-paginator
Also there are special pagination techniques for databases with millions of records, basically you
use greater than a certain index and less than. LIMIT in mysql get less efficient as a database grows.
Step one should be getting away from active record (eloquent) and use pdo direct (getPdo()) the pdo instance in laravel.
In fact I used to export data monthly, had an odbc setup on local and did monthly reports in MS Access, much more efficient.
You are at that phase where you are seeing there's a big difference in a small few hundred records verses a huge data set.