In a menu, the absolute maximum that a user should need to read while scanning for their required option is one word, so without icons you should put the most informative word first. An icon could indeed make scanning more efficient, but only if you can contrive to make the icons intuitively suggestive of the content. In the above scenario this would be tricky to do, as you have a lot of items on the 2nd level (i.e. icons for shirts would look way too similar to icons for sweaters to improve scanning speed).
I would suggest that instead of putting in an icon per individual menu option, you could put in one per section (where you have the separating lines). This would help the user to navigate the sections quickly without having to read too much text, and then you would be relying on the "one word" principle for a much smaller set of menu options.
If you are referring to the image on the side, I would say to be careful putting this in a 2nd level menu. I think that something like this can look good on a main page (where the menu options controlling it are in a single column), but in the example above the graphic on the right is too far away from the menu options in the left column to provide intuitive feedback. I imagine it would be more distracting than anything else to have a graphic flicker and change so far away from where the user is focused.