MySQL partitioned tables?
Partitioning could quite possibly help you in this situation.  By putting the data into a partition, the database will have a smaller table for each client to deal with.  This could help performance a lot.

Here is an example of how it would help.  The data in the table would otherwise be interleaved, so different clients would have rows on a data page.  Reading the data from a single client would then "clutter up" the available page cache with records from other clients.

However, it will not help very much if all the clients are accessing data concurrently, so all are competing for available memory.  Partitioning probably will not make this worse, but it won't necessarily help.

Also, MySQL automatically partitions the indexes on the table, which is generally a good thing.

Often partitioning is applied to a date field, so older data gets put into less used partitions.  This may be a case where another field is useful.  But, if all the clients need all their data at the same time, then the partitioning may not give you much of a gain.