In this paper, we study the spectrality and frame-spectrality of exponential systems of the type E(Lambda, phi) = {e(2 pi i lambda.phi(x)) : lambda is an element of Lambda} where the phase function phi is a Borel measurablewhich is not necessarily linear. Acomplete characterization of pairs (Lambda, phi) forwhich E(Lambda, phi) is an orthogonal basis or a frame for L-2( mu) is obtained. In particular, we show that the middle-third Cantor measures and the unit disc, each admits an orthogonal basis with a certain non-linear phase. Under a natural regularity condition on the phase functions, when mu is the Lebesgue measure on [0, 1] and Lambda = Z, we showthat only the standard phase functions phi(x) = +/- x are the only possible functions that give rise to orthonormal bases. Surprisingly, however we prove that there exist a greater degree of flexibility, even for continuously differentiable phase functions in higher dimensions. For instance, we were able to describe a large class of functions. defined on R-d such that the system E(Lambda, phi) is an orthonormal basis for L-2[0, 1](d) when d >= 2. Moreover, we discuss how our results apply to the discretization problem of unitary representations of locally compact groups for the construction of orthonormal bases. Finally, we conclude the paper by stating several open problems.