"Tell off" is more common, but I think it's also more harsh, so there are some circumstances where I wouldn't use it. For example, we say that parents "scold" or "reprimand" (or even "yell at") their children, but I would be a bit surprised if I heard a parent say that he/she had "told off" a child. As another example, if you arrived late for work, your boss might "scold" or "reprimand" you. To "tell someone off" doesn't sound like very professional behavior.
The meaning of "tell off" might be less harsh in the UK. GuideDogSaint is from the UK, and he says "scold" and "tell off" have the same meaning. Greg and I are both from the US, and we both think the words are a bit different.