If the performance doesn't improve, it is because your drive started fragmenting when free space got low. If it doesn't recover now that you've freed some space, you'll either need iDefrag or to reformat your drive and restore from backup or do a drive clone to another drive, and then back. If you use a cloner, make sure it is one which claims defragmenting as a side effect.
How low did free space actually get?