The UK is still part of the EU. So I am wondering, what is the legal basis of the decision to remove the words 'European Union' from the cover of UK passports issued since March 29th 2019 (the original date set for the UK leaving the EU)?
In short: putting it on to begin with is optional.
Quoting a European parliament answer to a similar question (emphasis mine):
What is commonly called an ‘EU passport’ is in fact a national passport established under the national laws of the Member States and issued to their citizens. Under EC law(1) only the security features and the biometric identifiers included in the passport chip have been harmonised on a legal basis relating to the Schengen acquis on crossing the external borders.
The current format of the EU passport contains common features on which Member States have agreed in non-binding resolutions(2) such as for example paper size, the burgundy coloured cover, similar typeface for name and the use of the words ‘European Union’ in the country's official language on the cover. This can be seen as contributing to citizens' identification with the EU and raising their awareness about their common status as EU citizens.
Refs 1 and 2 are:
Council Regulation (EC) No 2252/2004 of 13.12.2004 on standards for security features and biometrics in passports and travel documents issued by Member States; OJ L 385, 29.12.2004, p. 1-6 — as amended.
23.6.1981 — Resolution of the Representatives of the Governments of the Member States of the European Communities, meeting within the Council of 23 June 1981, OJ C 241, 19.9.1981 p. 1-7.
Both the Burgundy color and the words 'European Union' are recommended as part of passports issued by member states, but neither are compulsory.
As such, the legal basis of the UK's decision is: there's no legal basis for this to be illegal.