We consider issues of stability of time-discretization schemes with exact treatment of the linear part (ELP schemes) for solving nonlinear PDEs. A distinctive feature of ELP schemes is the exact evaluation of the contribution of the linear term, that is if the nonlinear term of the equation is zero, then the scheme reduces to the evaluation of the exponential function of the operator representing the linear term. Computing and applying the exponential or other functions of operators with variable coefficients in the usual manner requires evaluating dense matrices and is highly inefficient. It turns out that computing the exponential of strictly elliptic operators in the wavelet system of coordinates yields sparse matrices (for a finite but arbitrary accuracy). This observation makes our approach practical in a number of applications. In particular, we consider applications of ELP schemes to advection-diffusion equations. We study the stability of these schemes and show that both explicit and implicit ELP schemes have distinctly different stability properties if compared with known implicit-explicit schemes. For example, we describe explicit schemes with stability regions similar to those of typical implicit schemes used for solving advection-diffusion equations.