We study the loss of coherence of electrochemical oscillations on meso- and nanosized electrodes with numeric simulations of the electrochemical master equation for a prototypical electrochemical oscillator, the hydrogen peroxide reduction on Pt electrodes in the presence of halides. On nanoelectrodes, the electrode potential changes whenever a stochastic electron-transfer event takes place. Electrochemical reaction rate coefficients depend exponentially on the electrode potential and become thus fluctuating quantities as well. Therefore, also the transition rates between system states become time-dependent which constitutes a fundamental difference to purely chemical nanoscale oscillators. Three implications are demonstrated: (a) oscillations and steady states shift in phase space with decreasing system size, thereby also decreasing considerably the oscillating parameter regions; (b) the minimal number of molecules necessary to support correlated oscillations is more than 10 times as large as for nanoscale chemical oscillators; (c) the relation between correlation time and variance of the period of the oscillations predicted for chemical oscillators in the weak noise limit is only fulfilled in a very restricted parameter range for the electrochemical nano-oscillator.