He didn't know they had copies (assuming they even did; I think it's more likely they were able to reconstruct the deleted data, given that deleting a file is just removing its dirent, and formatting a drive is just recreating the filesystem metadata). As far as he knew, the entries in his browser history were the only records of those searches, or whatever.

That makes the action (assuming it was done with intent to destroy the evidence, and not merely an automatic, "quitting the browser purges its history" type thing) illegal.

Consider the analogous situation of two companies, both engaged in illegal activities:

Company A has a standing, published document retention policy that says that all financial records must be destroyed after 30 days.

Company B has someone sneaking in at night to shred the records of their profits from selling meth to schoolchildren.

The Feds have copies of both of their records, because they have someone on the inside copying them and turning them over.

One company's relevant employees are going to face one set of charges. The other's are going to face two. Can you guess which is which?