Probably because of the French origin.

В українській мові, крім родів (чоловічий, жіночий, середній) є ще відмінки. Кожен рід має свої правила формування закінчень в них. "майонез" - чоловічий рід.

Відмінки: http://aztekium.pl/vidminki.py?szukaj=майонез&lang=uk

називний (що?) майонез

родовий ( чого (немає)?) майонезу

давальний (кому?) майонезові

знахідний (що (знайшли) ? ) майонез

орудний ( чим?) майонезом

місцевий (у/на чому ?) майонезі

In short, when you're "using" them. The hint is in the name "Instrumental case" -> instrument -> using.

There is always instrumental case in "with ..." -> "з ..."

Think of "with mayo" as using mayo :D

(at least works as a memo aid in this case)