"sich entscheiden" or "sich entschließen" means to decide, "sich überlegen" means to think about or to consider. These are the "base meanings" as you have found out yourself.
The way you suggest to use "sich überlegen" is a figurative one: the result of some consideration is typically a decision. By mentioning the former you imply the latter, similar to saying e.g. "I went to the cinema" and implying that one not only went there but also watched a movie.
Notice that in this case "sich überlegen" is regularly used in Perfekt. From @tofros answer:
Ich überlege [mir], nach Asien zu reisen.
Using the Präsens suggests that the decision has not happened yet and the consideration is still taking place.
Ich habe mir überlegt, nach Asien zu reisen.
The consideration is already over and a decision (to either go or not to go) was made. The way I'd understand this sentence is: the decision has been made but one is not on his way yet (or might never be if the decision is not to go).