Hey sidebrnz,

You should be using DOSBox instead of Wine to run this game. Here are some helpful step-by-step guides that you can read to make it work:

http://www.gamersonlinux.com/forum/threads/heroes-of-might-and-magic-1-2-guide.403/
http://www.gogwiki.com/wiki/Heroes_of_Might_and_Magic_2:_Gold_Edition

First download the game installer from the website and install the game using Wine to get access to the game files, then you can follow the steps of any of the guides linked above.

Sadly I cannot offer any official solution as this product is not supported on Linux.

Good luck!