Tanto tortilla de patatas como tortilla de patata son formas válidas. En la primera se toma patata como contable y en la segunda como no contable. También se le llama tortilla española y tortilla a la española. Para tortilla española el DRAE da la definición:
- tortilla en la que se cuajan huevos con patatas previamente fritas.
La forma mayoritaria en el uso es en plural: tortilla de patatas. Estos son los datos de Ngrams:
En el CORDE también es mayoritaria la variante en plural, con casos del siglo XIX como:
- ... se comía su tortilla de patatas y su chuletita de ternera (Galdós, Mendizábal, 1898)
- Lo mismo que se hace una tortilla de patatas o de setas, o de puré de guisante... (Ángel Muro, El Practicón: tratado completo de cocina, 1894)
El primer registro de tortilla de patata en el CORDE es de 1968.