This is not a bug, but rather the link was removed intentionally.
While making some changes to the header, I decided that the link wasn't really useful for anything, except for one specific use case, because everything had already been covered: category links are on every page, category descriptions can be accessed with one click, a link for editing categories is on every category page too. The only thing that hadn't been linked anywhere was the Add Category route.
On the contrary, it was an additional high-priority menu item, which was distracting from other, generally more important pages, such as Users or Search.
Hence I removed the link from the header and added an Add Category item to the admin panel. Because the page might still be useful to some people in some use cases, I decided not to completely remove the page, though.