I don't believe there is much of a difference between "legalize" and "decriminalize," at least the way you mean. As I understand the common use, the difference is basically one of extent. As I understand it, decriminalization refers to removing criminal
penalties (not necessarily all
codified restriction), whereas "legalization" refers to removing all codified illegality, even where criminal penalties may not be present.
I agree semantics are important. I would suggest that when you say "decriminalize," what you really mean is "deregulate," or maybe even "delegislate."
But I could be wrong.
Edit: A google search returns interesting results. In seems that, when discussing prostitution, the words are commonly used as akpoff describes them. Whereas, when discussing drugs, the words are often used as I describe them.
Further edit: I think, to be clear, I will, from now on, use the phrases "legalize and regulate" and "decriminalize and deregulate." That way there can be no ambiguity.