Yes, you should include all computational steps in working out the computational complexity.
The complexity will depend on the method being used to calculate the MLE. For example, the MLE for the mean of a Bernoulli distribution is just the sample mean, which can be calculated in $O(N)$ (assuming that each arithmetical operation takes effectively constant time).
In cases where there is no analytical solution to the likelihood equations, it might be necessary to use iterative numerical methods. The computational complexity will then be affected by the number of iterations performed, which will depend on the desired precision. Wikipedia has an article listing some iterative procedures for MLE calculation.