What territories were lost or abandoned after Trajan?

The empire was at its greatest extent under Trajan.

Borders of the Roman Empire on Wikipedia is poorly sourced, but a few maps are useful:

So, who added or created imperial provinces?

Under Trajan

• 106 AD – Arabia, formerly the Kingdom of Nabataea, it was annexed without resistance by Trajan (imperial propraetorial province)
• 107 AD – Dacia "Trajana" (the Romanian regions of south-eastern Transylvania, the Banat, and Oltenia), conquered by Trajan in the Dacian Wars (imperial proconsular province). Divided into Dacia Superior and Dacia Inferior in 158 by Antoninus Pius. Divided into three provinces (Tres Daciae) in 166 by Marcus Aurelius: Porolissensis, Apulensis and Malvensis (imperial procuratorial provinces). Abandoned by Aurelian in 271.
• 103/114 AD Epirus Nova (in western Greece and southern Albania), Epirus was originally under the province of Macedonia. It was placed under Achaia in 27 BC except for its northernmost part, which remained part of Macedonia. It became a separate province under Trajan, sometime between 103 and 114 AD and was renamed Epirus Nova (New Epirus) (imperial procuratorial province).
• 114 AD – Armenia, annexed by Trajan, who deposed its client king. In 118 Hadrian restored this client kingdom
• 116 AD – Mesopotamia (Iraq) seized from the Parthians and annexed by Trajan, who invaded the Parthian Empire in late 115. Given back to the Parthians by Hadrian in 118. In 198 Septimius Severus conquered a small area in the north and named it Mesopotamia. It was attacked twice by the Persians (imperial praefectorial province).
• 116 AD – Assyria, Trajan suppressed a revolt by Assyrians in Mesopotamia and created the province. Hadrian relinquished it in 118.

Under Septimius Severus

• 193 AD – Numidia, was separated from Africa Proconsularis by Septimius Severus (imperial propraetorial province).
• 194 AD – Syria Coele and Syria Phoenice, Septimius Severus divided Syria into these two units in the north and the south respectively. Imperial provinces (proconsular and propraetorial respectively).

Illustratively animated here:

_{Src: EmperorTigerstar: "The History of the Romans: Every Year" – Youtube}

_{Note that Roman expansion and colonisation attempts for example into Germania are just left white and several other outward campaigns are not depicted above as well. Particularly in the East very faint patches of light colour pop up from time to time. Not easy to spot but adequate to illustrate the effect.}

Why the difference between territory mapped as Trajan's empire and all the swathes of land conquered under Severus?

It is just the other way around as presented here so far: what Trajan conquered Hadrian either gave up or stabilised effectively. The Romans rode out to fight regularly, and sometimes even won. But forward lines of defense, client kingdoms and dependent areas are not the same thing as a regular province, fully under imperial jurisdiction and fully integrated over a long time. Incursions were possible, coming from the outside in and sometimes being defeated, pacified, integrated – or slowly chipping away a bit of imperial authority after Trajan.

While the amount of territory under Roman military control might be a bit bigger under Severus, the established borders of the empire were not.

^{Src: WP – Severus
The frontier of Roman Africa (dark tan) in the late 2nd century AD. Septimius Severus expanded the Limes Tripolitanus dramatically (medium tan), even briefly holding a military presence (light tan) in the Garamantian capital Garama in 203. Much of the initial campaigning success was achieved by the legate of Legio III Augusta, Quintus Anicius Faustus.}

In Caledonia:

Septimius Severus died in York in February 211, leaving the conquest of Scotland incomplete. One of his sons murdered the other and returned to Rome to claim the Empire, but was himself murdered some six years later. Hadrian’s Wall continued as the Roman frontier in Britain, and Scotland remained unconquered.
_{–– Rebecca Jones: "Scotland’s African Emperor", Archaeology/History, Historic Environment Scotland, 18. Oct 2017.}

The overall assessments are certainly not rosy:

Besides, he had expanded the entire army, not merely in the Rome garrison and by raising three legions: new auxiliary regiments were formed. His frontier policy demanded more troops, for he was indeed a propagator imperii. In Africa there was a new forward line, in Mauretania, Numidia and Tripolitania; in the east two new provinces beyond the Euphrates, extension of Syria down the river and into the desert, extension of Arabia. Perhaps—it is now doubted-he pushed the eastern limits of Dacia out beyond the Aluta. He very decisively altered the shape of the empire, weighting it much more towards the east (and to a lesser extent his native ‘deep South’). The long-term effects of this are not negligible. At the end of his life he was in the far west, trying to repeat the conquests of Agricola. That part of his policy was aborted by his death. Still, the British campaign, manifestly intended to conquer the whole island, could be dismissed as motivated solely by ‘desire for glory’ with more justice than the annexations beyond the Euphrates to which Dio applied this judgement. Mesopotamia and the other extensions of territory in the east were worth more to Rome than Caledonia, as Caracalla recognised. Caracalla also tried to tackle the Alamanni –perhaps his father should have dealt with the northern frontiers, rather than succumb to the lure of the fabled island.

Given the chaos into which the empire descended in the third century, and the contrast, grim in many respects, between the Antonine era and the new world that was to emerge, it is not surprising that Septimius Severus has been pilloried. His was by far the longest reign of any emperor between the death of Marcus in 180 and the accession of Diocletian in 284. ‘The contemporaries of Severus, in the enjoyment of the peace and glory of his reign, forgave the cruelties by which it had been introduced’, wrote Gibbon. ‘Posterity, who experienced the fatal results of his maxims and example, justly considered him as the principal author of the decline of the Roman empire.’ Such a verdict, in the fifth chapter of the mammoth work, may seem over-hasty (Gibbon was to find other villains, such as Constantine, in later pages). But the decline set in soon enough, even if the fall was long postponed. Was it Septimius’ doing?
_{–– Anthony R.Birley: "Septimius Severus. The African Emperor", Routledge: London, New York, 1971.}

If we look at the amount of control the Romans wielded over the fabled Caledonia, we see quite a low contrast to the most strikingly Wikipedia page in bold colours.

How many soldiers Albinus took from Britain is debated. He pre- sumably did not remove all of them, and would probably have arranged for the protection of the cities and the coasts in case he was driven back to the island. What he did on the northern British frontier is problematic; a few factors seem to point to a large-scale evacuation of Hadrian’s Wall: firstly, it could be argued that there was trouble in Britain as a result of the withdrawal of troops, followed by the expedition that Severus undertook in Britain from 208 to 211 to restore order in the north of England and to subdue Scotland, but the fact that there was no Imperial activity on this scale for over a decade rather negates the urgency of the affair. Secondly, archaeological investigations reveal that Severus undertook large-scale repairs to Hadrian’s Wall; and thirdly, the Wall garrisons of the late second century are not represented in the lists of units which are known for the third century, all of which makes it seem as though all the troops had been removed and then new ones reinstated. Detractors accuse Albinus of stripping the garrison of Britain to the bone to provide a large enough army with which to face Severus. The three British legions and the auxiliary troops would not provide anything like the numbers he needed, even if he took all of them across the channel. But Britain was not totally lost after Albinus’ expedition, so it is assumed that he left some sort of garrison there, and then augmented his army by recruiting more men in Gaul.
_{–– Pat Southern: "The Roman Empire from Severus to Constantine", Routledge: London, New York, 2001.}

To recapitulate with maps of varying accuracy:

Caledonia/Scotland cannot really count as it was of too sparse an interest to be romanised. The African conquests of Severus were of dubious value and also temporary.

Mesopotamia and Armenia are a special case. While the acquisitions of Trajan were immediate, officially lost, and perhaps should not really be counted at all, it is said the Severus made Roman Mesopotamia a permanent Roman province.
That is somewhat true, only that it was in a constant zone of conflict and, furthermore the new province has the name of the old, but by far not its extent. It is geographically quite different to claim 'to be in possession of Mesopotamia' when at one time this gets to the shores of the Euphrates, includes Babylon and reaches of to the Gulf, or if you touch the Tigris in modern Syria and Turkey and declare it be the same in name and substance, despite being quite a bit smaller to begin with and with ever changing territorial borders.