I do not understand how this sentence translates as 'tastes like' - this bit is a bit confusing to me, could it be said as O sabor de ovo e mesmo uma peixe?
No. The meaning of the portuguese sentence was mistranslated into English. If one says "o ovo está com sabor de peixe" he probably wants to say that someone who had tried the egg felt like it was tasting like a fish at that moment. Maybe that egg was fried in the same oil some fish was previously fried too, then the egg tasted like fish. Got it?