The performance of indexes does not degrade linearly with the size of the table. Tables have to be seriously massive before that becomes an issue. If you are seeing performance problems, I'd start doing mysql 'explains' and making sure all your queries are doing the least amount of row scans they can do. You might be suprised at what the actual bottleneck ends up being.
So, basically, if you need the data, I wouldnt go messing around with it. On the other hand, if its something like session data, just delete the rows that are too old.