Als ik het goed begrijp, wil je niet de bestanden verwijderen maar de geschiedenis.
In je persoonlijke map staat een verborgen bestand met de geschiedenis, en wel in:
/home/JouwGebruikersnaam/.local/share/recently-used.xbel
Open dat als volgt met kladblokje Leafpad:
leafpad ~/.local/share/recently-used.xbel
Druk op Enter.
Maak het helemaal leeg (wis alle tekst), sla het op en meld je af en weer aan. Open Parole en kijk of de geschiedenis weg is.
Ik kan nu niet controleren of dit werkt, maar ik vermoed dat dit het oplost.