I always thought menus had icons so they could be matched to the same functionality on the toolbar. If a menu lacks an icon, then it's probably not on the toolbar. This falls apart when there is no toolbar. But I have definitely found an action in the menu, looked at the icon, and matched it to a a button elsewhere.
I believe some programs used to let you even drag menu items to the toolbar.
I believe Microsoft Office 97 for Windows was the first time I saw icons next to menu items. Office 97 had highly customizable menus and toolbars. Each menu item and toolbar item could be thought of as an action with an icon and a label, and that action could be placed in either a menu or a toolbar. Not every menu item had an icon associated with it. Additionally, each icon was colored and was clearly distinct.