Problem solved (THX to guys from forum.ixbt.com)
Just how it goes:
1. Rename patch file (kinda patchorsomething.exe) to patchorsomething.zip (actually, it IS a .zip).
2. Extract it somewhere.
3. Manually replace every file in Mafia game folder that you can with extracted files (overwrite, if prompted).
4. Put the rest files from Patch folder directly in Mafia game folder and forget about them.
5. Game is patched now, enjoy (maybe you'll need to find No-cd-fixed-exe stuff to play, I did).
Regards, Nick.