Please define "fair share." That is such a loaded term because it implies that the only benefit of a company to people is in the tax revenue it provides a government.
We could reframe that argument to say that Google should provide a fair share of jobs to the unemployed. Billions of revenue but far fewer employees than some companies half the size. Clearly Google isn't hiring a 'fair share' of workers right?
We can ride this all the way into absurdity. We shouldn't be judging companies by opinion-based metrics like "fair share" but instead on their net economic contribution to the economy -- not their contribution to a government.
If Google paid zero tax, the economy is far better off with them than without them; look at the jobs it provides (and the economic activity those generate,) look at the return on investment to shareholders (which helps those shareholders earn money they can invest in other ventures.)
It isn't all about taxes. Google spends money far more effectively than government. Google should pay taxes at an amount commensurate with the public goods they consume -- not a cent more. Remember, taxes aren't ever paid by companies -- they are paid by individuals. You raise taxes on Google, you raise taxes on every person with any sort of relationship with Google.