...Where somecol BETWEEN thisval AND thatval...Order By anothercol ...performance often suffers. Often the optimiser looks for an index it can use for the range condition, and that can be quick. But the index used for the range condition won't help with ordering, so the optimiser resorts to filesort for ordering the result. If the whole resultset fits in memory, that may be fast enough, but if the sort has to go to disk, performance will suffer.
So you may have to put up with slow range filtering, or slow ordering. How to make that choice? If the range condition is highly selective, ie it selects a tiny proportion of rows, that index is likely preferable; otherwise try an index on the ordering column.
More discussion of this is at http://explainextended.com/2009/04/01/choosing-index/.