No it was most probably not made by Muhammad Ali
Searching the web, and I haven't been able to find anywhere he actually said it. Only things I find is the adidas ad. Looking at the words "Impossible is nothing" through books it only appeared after 2004.
Google Ngrams search for Impossible is nothing
Looking at wikiquotes and the impossible quote is not listed there. When looking at the web, it's probably the most famous quote "by him", so it's very surprising it's not listed by wikiquotes, if he actually said it.
"Impossible is Nothing" was the previous mainstream marketing slogan for Adidas. This campaign was developed by 180/TBWA based in Amsterdam but also with significant work being done by TBWA/Chiat/Day in San Francisco – particularly for its basketball campaign "Believe in Five".TBWA\Chiat\Day commissioned Zane Peach[41] to produce images for 2007 international ad campaign.
Wikipedia link about adidas marketing
QuoteVadis: Impossible is nothing gives the credit for the quote to "— Anonymous for Adidas advertisement campaign."
The quote is probably made by Adidas and not Muhammad Ali, but I don't have conclusive proof.
The quote might have been made by John C. Maxwell in his book THE DIFFERENCE MAKER; page 53(Credits to Urthone), I haven't found the full quote in use before that time.
“Impossible is just a big word thrown around by small men who find it easier to live in the
world they’ve been given than to explore the power they have to change it. Impossible is not
a fact. It’s an opinion. Impossible is not a declaration. It’s a dare. Impossible is potential.
Impossible is temporary. Impossible is nothing.” Page: 53