Can I develop software that solves a problem as a Master's thesis?
Methodology, models and algorithms

Usually in such research the majority of the work spent will be on the software, but the majority of written thesis will be about the problem analysis, literature review of similar problems in the field, methodology, models and algorithms used, and the evaluation of the proposed solution to the problem.

Yes, there's some software engineering involved, but that's generally not research; however, there are research questions related to that software - the actual tool demonstrates the feasibility of your proposed method (that your solution can be implemented) and the applicability of your proposed method (that your solution is useful for achieving the targeted goal), but it itself will often be "just" an appendix to the research work. In particular, there's a big impact on novelty. Building software that essentially reimplements an existing tool can be commercially useful, but doesn't constitute novel research no matter how much work it takes, while doing an adjustment to an existing open-source system that takes just a small bit of programming but implements a substantially different (and better in some aspect) method is novel research. I mean, there are algorithms that differ from existing ones by just a line or two of code but have a substantial impact on how they behave, and you could definitely build a thesis on such an improvement.

It's like the "method and apparatus" in patent applications - developing the method and apparatus is novel research; actually building it often will be helpful, but isn't strictly necessary and (by itself) wouldn't constitute novel research.