Many times during conversation I hear the phrase Don't mistake me. Is it grammatically correct when used to mean Don't take negative connotation of my word. Shouldn't they say Don't take me by mistake?
Don't mistake me is perfectly grammatical, but it doesn't mean anything like "please don't interpret my words negatively". When mistake is used as a verb, it means "identify incorrectly" or "misinterpret". Thus, you can get usages such as:
Don't mistake me for my sister.
Don't mistake me: I'm not disagreeing with what he said, but he could have expressed himself more politely.
I think the phrase you may be looking for is "take amiss" (like FumbleFingers said).
Please don't take my words amiss, they were not meant to offend.
Don't mistake me is perfectly valid in certain contexts. It is usually used with an object that describes what you do not want to be confused with, as in
Don't mistake me for a fool.
Don't take me by mistake. can also be used, as in
Take the prisoner to jail. Don't take me by mistake.
In general, the prefix mis is used to change the meaning of a verb to one that implies that the action / state was somehow erroneous, incomplete, or bad. The reason there are different meanings for mistake is that there are different meanings for take.