If you define patterns as anti-patterns just because there are some situations where it does not fit, then YES it’s an anti pattern. But with that reasoning all patterns would also be anti patterns.

Instead we have to look if there are valid usages of the patterns, and for Service Locator there are several use cases. But let’s start by looking at the examples that you have given.

public class MyType
{
    public void MyMethod()
    {
        var dep1 = Locator.Resolve<IDep1>();
        dep1.DoSomething();

        // new dependency
        var dep2 = Locator.Resolve<IDep2>();
        dep2.DoSomething();
    }
}

The maintenance nightmare with that class is that the dependencies are hidden. If you create and use that class:

var myType = new MyType();
myType.MyMethod();

You do not understand that it has dependencies if they are hidden using service location. Now, if we instead use dependency injection:

public class MyType
{
    public MyType(IDep1 dep1, IDep2 dep2)
    {
    }

    public void MyMethod()
    {
        dep1.DoSomething();

        // new dependency
        dep2.DoSomething();
    }
}

You can directly spot the dependencies and cannot use the classes before satisfying them.

In a typical line of business application you should avoid the use of service location for that very reason. It should be the pattern to use when there are no other options.

Is the pattern an anti-pattern?

No.

For instance, inversion of control containers would not work without service location. It’s how they resolve the services internally.

But a much better example is ASP.NET MVC and WebApi. What do you think makes the dependency injection possible in the controllers? That’s right — service location.

Your questions

But wait a second, if we were using DI approach, we would introduce a
dependency with another parameter in constructor (in case of
constructor injection). And the problem will be still there.

There are two more serious problems:

1. With service location you are also adding another dependency: The service locator.
2. How do you tell which lifetime the dependencies should have, and how/when they should get cleaned up?

With constructor injection using a container you get that for free.

If we may
forget to setup ServiceLocator, then we may forget to add a new
mapping in our IoC container and DI approach would have the same
run-time problem.

That’s true. But with constructor injection you do not have to scan the entire class to figure out which dependencies are missing.

And some better containers also validate all dependencies at startup (by scanning all constructors). So with those containers you get the runtime error directly, and not at some later temporal point.

Also, author mentioned about unit test difficulties. But, won’t we have issues with DI approach?

No. As you do not have a dependency to a static service locator. Have you tried to get parallel tests working with static dependencies? It’s not fun.