First and foremost, to understand Xelloss' power, you must understand the hierarchy of the mazoku. Below is a small chart I have comprised to further better understanding of this hierarchy:
The Lord of Nightmares is God. She created everything. She created Ruby Eye Shabranigdu, the Dark Lord of the world where Slayers takes place. In turn, Shabranigdu created five subordinates of his own: Mei-oh Phibrizo, Juu-oh Zelas Metallium, Maryuu-oh Gaav, Kai-oh Dolphin and Ha-oh Grausherra. With the exception of Juu-oh and Ha-oh, each mazoku lord created a priest and a general for himself. In Ha-oh's case, he created two priests and two generals and in Juu-oh's case, she created only one priest.
In the process of creating a priest and a general, each mazoku lord will remove a piece from himself that is equal in size to those of the other mazoku lords. The power is then divided into new beings. In most cases, the power removed is divided up into four (or more) beings. Since Juu-oh created only one priest, she did not need to divide her power further, unlike the other mazoku lords.
Therefore, Xelloss is stronger than any other general alone. In terms of hierarchy, he is third ranked (Shabranigdu being first, the mazoku lords second). Anyhow, onto Xelloss' abilities. Being a high ranked mazoku, Xelloss has immense power. He is more powerful than Lina Inverse when she is not using the power of the Lord of Nightmares.
A mazoku's true self exists on the astral plane. The Xelloss that Lina sees is just an image projected onto the physical plane. This existence is what gives Xelloss the ability to teleport and renders physical attacks against him useless. In order to teleport, Xelloss simply plucks his image off of the physical plane and puts it back down at a different set of coordinates. This is why we never see Xelloss fighting any important battles with other high ranked mazoku: they generally move back and forth between the physical and astral plane at great speeds.
Normal physical attacks are useless against Xelloss. Your average swordsman will have a tough time hurting Xelloss at all... in fact, so will your average sorcerer. Even Lina wouldn't be able to hurt Xelloss using her magic. Like Valgarv, Xelloss could probably take a boosted Dragon
Slave right inside of him! The only way Lina would be able to harm Xelloss would be to use the Giga Slave or the Laguna Blade (both spells call on the Lord of Nightmares' power). As for swordsmen... the Hikari no Ken would have a chance of hurting Xelloss if used properly. It all depends on the power of the individual. Keep in mind that if Xelloss was a less powerful mazoku, it would be easier to harm him (obviously).
A misconception that people often have is that Xelloss uses magic. While he certainly has the capabilities of using magic, he doesn't. He would prefer to rely on his own power. To use an outside source of power would be saying that his own power isn't good enough and that would be a lack of self-confidence... and thus it would be human to think so (remembering that mazoku look down upon humans). In any case, we have seen Xelloss casting the Blast Bomb. While he does not need the Demon Blood Talismans to cast magic, he used them because he knew Lina was watching and he knew that she would want them to become more confident in casting the Giga Slave (as according to Mei-oh Phibrizo's plot to destroy the world using Lina as his tool). Thanks to Hilary Lile for the information on the Demon Blood Talismans.
Moving onto a more interesting topic, Xelloss cannot be killed. If he becomes severely wounded he'll retreat back into the astral plane for a while and regenerate. He'll eventually come back. Xelloss' regeneration powers are fairly strong and even after taking a beating from Maryuu-oh Gaav he was back in the game approximately a few hours later. In order to keep a mazoku from coming back, the mazoku must be ruined. Being ruined is having its complete identity torn apart. Maryuu-oh Gaav was ruined by Mei-oh Phibrizo, for example. In any case, I guess you could compare Xelloss to a cockroach: annoying and hard to get rid of. ^_^;