Effective identification of polynomial input-output models for applications requiring long-range prediction or simulation performance relies on both careful model selection and accurate parameter estimation. The simulation error minimisation (SEM) approach has been shown to provide significant advantages in the model selection phase by ruling out candidate models with good short-term prediction capabilities but unsuitable long-term dynamics. However, SEM-based parameter estimation has been generally avoided due to excessive computational effort. This article extends to the nonlinear case a computationally efficient approach for this task, that was previously developed for linear models, based on the iterative estimation of predictors with increasing prediction horizon. Conditions for the applicability of the approach to various model classes are also discussed. Finally, some examples are provided to show the effectiveness and computational convenience of the proposed algorithm for polynomial input-output identification, as well as the improvements achievable by enforcing SEM parameter estimation. A benchmark for nonlinear identification is also analysed, with encouraging results.