We develop an implicit discretization method for pricing European and American options when the underlying asset is driven by an infinite activity Lévy process. For processes of finite variation, quadratic convergence is obtained as the mesh and timestep are refined. For infinite variation processes, better than first-order accuracy is achieved. The jump component in the neighborhood of log jump size zero is specially treated by using a Taylor expansion approximation and the drift term is dealt with using a semi-Lagrangian scheme. The resulting partial integro-differential equation is then solved using a preconditioned BiCGSTAB method coupled with a fast Fourier transform. Proofs of fully implicit timestepping stability and monotonicity are provided. The convergence properties of the BiCGSTAB scheme are discussed and compared with a fixed point iteration. Numerical tests showing the convergence and performance of this method for European and American options under processes of finite and infinite variation are presented.