Index for ORDER BY on aggregate in MySQL
I have one suggestion, and if that doesn't work, then you're probably going to have to denormalize it.  There's no way to optimize a sort of the result of an aggregate function, because the entire set has to be calculated and sorted by the ORDER BY before a LIMIT ... OFFSET can be applied.  

The database is theoretically free to return any of the possible valid rows to satisfy the LIMIT ... OFFSET when there's no explicit ordering in the query.  Some would argue that the existence of OFFSET isn't even a legitimate concept in a purist sense of the relational model, since tuples aren't ordered in a relation... but I digress.

You're limited on how an index can help you, primarily because you're doing GROUP BY one thing followed by ORDER BY something different -- you're already twisting the data in two directions, so even if the query were less complicated but had these two conflicting requirements, you'd have this same problem.

To explain your EXPLAIN (you might want to add the headers from the explain, to your question).

type index this is the first potentially-confusing piece of info; this is called the join type, and index here doesn't mean the query is using an index in the way you might expect; in fact, it has two different meanings, both of which are essentially full table scans with more or less help from an index, but not for lookups.  In this case, since Extra doesn't say Using index, the optimizer has chosen 'index_leads_on_user_id' (as shown in key) so that it can do the full table scan in index order -- reading the rows from the table in the order that the rows appear in that index... so it's reading from your table in "group by" order with the help of that index (on user_id).

possible_keys are the keys the optimizer found potentially viable for finding the records.  It notices both "index_leads_on_promo_id_and_user_id" and "index_leads_on_promo_id" because "promo_id" is the leftmost column in each of those indexes, so they could have been used to filter out only the 3 values for promo_id that you needed.  The optimizer, though, has abandoned this route, having apparently determined that the ability to read the rows in GROUP BY order would be more efficient than plucking out the matching rows and then having to sort the result for the purpose of grouping.

key is the index MySQL actually selected, for reasons I mentioned above.  Since the selected one couldn't be used to filter rows, it's not listed among possible_keys.

key_len 4 is number of bytes from the left side of the selected index that the optimizer will actually consider.  With a multi-column index, the first non-useful column counting from the left elimiates the use of any columns to the right; for a single column index on an INT, here, all 4 bytes are used.

ref NULL indicates that no column or value is being compared to the selected key.

extra: Using where because the WHERE clause will have to be used to remove all of the rows because we're doing a full table scan that will return more rows than are needed; Using temporary because a temporary table is needed to hold the GROUP BY result so that it can be sorted into a different order; Using filesort is how the server will store all of the useful records not filtered by the where clause.

The bottom line here is the that query seems about as well-optimized as it can be.



Also, the query itself is also not entirely logically valid.  It's syntactically correct enough that MySQL will run it, but it's ambiguous and may be causing extra work for the server and it could be distracting the optimizer.

SELECT *, SUM(entries_count) AS entries_count FROM leads
...
ORDER BY entries_count DESC


You can't SELECT * ... which includes a column called entries_count ... and then another column that you're aliasing AS entries_count... and then ORDER BY the ambiguous name entries_count and expect to get an unambiguous result.  

Tested on MySQL 5.1 and 5.5, I find that this query sorts by a random value from the physical column and not by the SUM() result, and returns two different columns, both called "entries_count" in the result set, which means, at minimum, the server is having to manipulate extra data that you can't use.  This is not valid and you should definitely try explicitly listing the columns you want, excluding the physical column entries_count, which is going to be a meaningless value in light of the GROUP BY, and then, keep it unambiguous at the end:

ORDER BY SUM(entries_count);