I assume it's a TiVo HD you are talking about and have moved this thread to the TiVo HD section.
The TiVo has very little RAM so almost every command including showing a menu is actually read from the hard drive.
Slow down of the system is usually because of hard drive issues.
Given you say you have had the TiVo for 4.5 years, it would not be unusual to start having issues with the hard drive, which is slowing down the read speeds.
This issue can be just clutter or the drive starting to fail.
If the shows are not that important to you, do a clear and delete everything. it will setup the TiVo as new.
If you don't want to lose the shows, replacing the drive/s is the other option, and given their age probably about time before they fail totally.