Hiya
Thanks guys, for replying so quickly. Good to know it isn't just my system that is experiencing the issue.
I understand that you can clear the history manually but this isn't the same as using CCleaner to clean it.
I will have to revert back to using Internet Explorer at the moment. This seems to be cleaning as expected.
Hopefully they will work out how to clean Edge soon.