__new__ method giving error object.__new__() takes exactly one argument (the type to instantiate)

    instance = super(Foo, cls).__new__(cls,*args, **kwargs)

is correct. However, you are responsible for first removing arguments that your class introduces, so that when object.__new__ is ultimately called, both *args and **kwargs are empty.

Your code should be something like

class Foo:
    def __new__(cls, a, b, *args, **kwargs):
        print("Creating Instance")
        instance = super(Foo, cls).__new__(cls, *args, **kwargs)
        return instance

    def __init__(self, a, b, *args, **kwargs):
            super().__init__(*args, **kwargs)
            self.a = a
            self.b = b

This definition removes your new parameters a and b from args before passing it on to whoever is next on the MRO. Likewise for __init__.