Hm. If I understand the cellophane paradox, it says that the "substitutes exist" does not imply "there is no monopoly".
That seems different from your argument, which I understand to be "only a monopolist would make it easy for consumers to choose a competitor". But again, the conclusion that Google is a monopolist seems to be baked into this logic -- would you really say Google is not a monopolist if they did not offer search engine choice?