I've assumed AVAST who bought Piriform, the original creators of CCleaner, are using it or a dedicated version as their browser cleaner. Maybe not but the problem the OP describes appeared to be strangely similar to that I've experienced for years when using CCleaner with recent versions of Firefox and Waterfox.
I've used older versions of CCleaner too and whatever the problem is it is not just a CCleaner issue, it only started with the post the Firefox Quantum revamp and more recent Waterfox versions whose browser cleaning efficacy seems to be tied into the Firefox version.
I have no idea where you have been looking or if you tried this search - https://www.google.co.uk/search?q=where+does+firefox+store+%22session+cookie%22+information
In the Firefox and Water fox user profile folders of course; these are two examples of paths I added years ago to the CCleaner INI configuration file that would originally get CCleaner to clean Firefox and Waterfox properly but keep wanted cookies. The Waterfox entries have to be identified as Firefox locations:-
CustomLocation5=FIREFOX|C:\Users\Username\AppData\Roaming\Waterfox\Profiles\xxxxxxxxx.default\sessionCheckpoints.json
CustomLocation6=FIREFOX|C:\Users\Username\AppData\Roaming\Waterfox\Profiles\xxxxxxxxx.default\sessionstore.jsonlz4
Since the Firefox Quantum update of Firefox (2017) the same configuration paths does not work anymore; cookies from the last session are not all removed even though the JSON files concerned are being reported by CCleaner as cleaned. Is that not similar to what
sooke2004 is describing?
Waterfox (Classic) which is derived from earlier Firefox versions is affected too.
Of course the sooke2004's problem maybe an entirely different issue. So if the AVAST One browser cleaner is not CCleaner then obviously my contributions here are irrelevant.
But as AVAST own both it would be odd if there was no connection. It just sounded as if it could be at least similar to the problem I've experienced with CCleaner and both Waterfox and Firefox, so worth posting about.