When people testify before congress like this, is it under oath? Lying to congress should be considered perjury.
Lying under oath has to be a clear and deliberate misrepresentation of the truth. That can't be proven in this case. It's a perfectly valid opinion to believe that Google is successful because it was first, whether you agree with that opinion or not.
No it isn't. It's factually false.
That said, you'd have to be clueless to think that there were no search engines before Google. Haven't they at least heard of Yahoo?
He is a lawyer acting as a PR flack, both professions where many express whatever opinions they are paid to express. It could well be possible to prove that he didn't believe what he was saying. Who knows what emails went around before his testimony.
What he said was certainly false, and he should have known that. For him to not actually know requires him to be competent enough to get hired by a top law firm, and competent enough to be selected by them to testify to Congress, but incompetent enough not to know basic facts about his topic. Such a person might exist, but Occam's Razor suggests that he was indeed competent enough to know the truth, but willing to lie to benefit his client because he (correctly) thought he'd get away with it.