I think "with potatoes" should be acceptable also; at least where i am in North America, saying "fish with potato" sounds incorrect (would need an indefinite article to mean just one potato, or if it's like mashed potatoes it would sound strange to use the singular).
Sounds weird to me as well. When saying such things usually it's more than one potato you are talking about.
I think in fact "do you eat fish with potatoe" would be grammatically correct (as well). I think there is even a name for it : the partitive, or something. In any case it sounds natural to me (from England) if you are talking in a general sense. I think the sense of the 'partitive' is 'a part' or example of something: do you eat with 'a part of, or example/instance of, potatoes in a general sense? The partitive singular would then be correct (I'm not sure if I have the grammatical term correct, though....): in any case it (as well as the plural) sounds correct to me as a Home Counties, Middle Class English person. I think therefore that both plural and single forms are correct in this case. (actually I/we should look it up....)
And no its not їсиш because it's an irregular verb .....please someone support me on this because I'm the worst of authorities on Ukrainian....