Those little colored corners are added separately as you may want to add other menu items that are not categories and attach them a color anyway.
To make it appear you need to set the desired hex color code in the description field of the menu item as explained in the documentation.
Getting Started > Adding Menus
Note: If you can't see the description field you can enable it by activating it from the Screen Options at the top right of the Appearance > MenusĀ admin page.