I understand that you are wondering why illegal immigrants are not more often deported by the authorities. This answer has grown a bit out of proportion because I also try to explore the general refugee situation. That seems appropriate because the large number of migrants makes the question of deportation more pressing. We would not be very concerned about just a handful.
Numbers
First of all, while in 2015 about a million migrants entered Germany, only 282,000 asylum requests were decided; a lot of them probably dated from 2014 (the asylum seekers often needed weeks to even file their request due to adminstrative overload). Of those 282,000, 90,000 were rejected. The others have been granted asylum or refugee status (there is apparently some distinction). This means that the vast majority of ("true" or "alleged") refugees who came to Germany in 2015 are waiting for their request to be processed.
Legal And Police Situation
Did many of those 90,000 stay in the country? I don't know. Possibly. Some may still be tolerated ("geduldet"), i.e. the deportation may have been postponed according to par. 60a AufenthlatsG. The remaining ones are indeed obligated to leave the country. They are informed of the decision and have to leave within a period of time between 7 and 30 days. If they don't leave, they will be subject to criminal prosecution because they violate par. 95 of the Aufenthaltsgesetz. Of course it's usually not known to the authorities that somebody is still — illegally — in the country. Short of raids or coincidental run-ins with the police, e.g. because of traffic violations, illegal immigrants fly under the radar here like in all other countries (I suppose you are aware of the current discussion in the U.S.).
I assume that illegal immigrants are not high on the priority list of the police, given that the cost/benefit ratio of actively searching them is probably quite bad; criminals solely due to status violations don't do much damage as such, compared to other criminals. One must assume though that some of the illegal immigrants will steal or deal drugs for a living, since they cannot officially work or receive subsidies; that exposes them to the authorities as much as other criminals, making it more likely to be caught.
Deportation
So the question which remains is what happens to the relatively small portion of migrants who are here illegally and who are found out. It seems easy: Deport them! The law provides the option to deport them without notice (because they would flee upon receiving a notice).
Deportation to the EU Border State
Migrants coming through other European Union countries should be processed at the port of entry, according to the Dublin Regulation. That was how Germany, with no external borders, cowardly used to shield itself from migrants. There is some legal debate whether an asylum seeker who against all Dublin Regulations reaches Germany (or even just the German border) can legally be turned away. A legal scholar in an interview in the current Spiegel magazine claims that every request must, according to European law, be at least checked first before the asylum seeker could be sent back to the port of entry.
The big problem here is that the current crisis overwhelmed the EU border countries, in particular the already struggling Greece (which has only 11 million citizens). German courts have forbidden to send asylum seekers back to Greece and a few Balcan countries because of their dysfunctional asylum processing.
Apart from the legal situation everybody just acknowledges that the Dublin Regulations were not meant to deal with the current number of refugees.
Therefore, sending refugees back to Greece is currently not an option.
That means asylum seekers will have their requests processed in Germany for now, a procedure which takes many months. There are no new numbers; mid-2015 the time was already about 5 months. Now it seems that you need already months to just file the request. The administration is hopelessly understaffed. New clerks need substantial legal and adminsitrative education so that it takes months or years from the top-level budget decision for new positions to when they are put to work.
Deportation to Their Home Country
Back to the question where to deport illegal migrants to.
For citizens of safe countries, that seems obvious. (As discussed, migrants from unsafe countries will be granted refugee status, or they will at least be temporarily tolerated.) But the migrants often destroy their papers and simply refuse to tell where they come from. Some countries flatly refuse to provide replacement documents for their own citizens; they also refuse to take anybody without papers back, effectively making it impossible to deport migrants to them who do not cooperate. That seems to be the case for some North African countries (cf. this German Spiegel article). The German government will probably have to pay the countries in exchange for them to take their citizens back.
Of course, deportations happen, and they are not pretty. Looking a little closer, a multitude of practical and legal problems emerge. First there is the fairly extreme effort to charter a flight and provide a couple police men, a doctor etc. to accompany the person. The migrants are frequently desperate, some hurt themselves to a degree which makes it impossible to transport them. If they are too desperate or violent, the pilots may not fly for safety or ethical concerns. Other passengers complain on regular flights. Doctors refuse to cooperate, or testify suicidal tendencies. Migrants have suffocated in police custody during a deportation attempt.
Conclusion
Legal Situation
I cannot see a wide-spread disregard for the law by the German government. If anybody is violating European law, it's Greece and possibly some Balkan states on the migration land route. But in all reality these smaller countries are totally overwhelmed, so the situation is more a factual impossibility to obey the law, which cannot be helped as long as the facts are what they are.
Note that the Dublin Regulations do not forbid Germany to welcome immigrants or accept requests for asylum. On the contrary: according to the legal scholar in the Spiegel magazine Germany has an obligation to at least minimally process asylum requests, once the asylum seekers have reached the border. (And since sending them back is not an option, the request is processed in Germany entirely.) There is no violation of the law there.
Practical Aspects of Deportation; Alternatives
At the end of the day forced deportations are an expensive, undignified, violent affair; I would simply consider it unsuitable for mass deportations. The authorities quickly reach the limit of what is doable with the current budget, personnel, and with respect to human rights — there is a legal and ethical limit to applicable violence against basically peaceful individuals. (I assume that Donald Trump has no idea what he is talking about when it gets to the ground work. "He has a big mouth and nothing behind it", as we say here.)
Bottom line: If somebody doesn't want to leave, there is little you can do in a free country. I do not think that the government has deliberately decided to ignore the law; it's rather that the law is hard to enforce. That happens a lot, if you think of it.
If one is adamant at making migrants leave, the only mass solution I can envision is to make it attractive to leave. I can imagine that 10,000 or 20,000 Euros per person is a sufficient incentive for migrants who did not flee from acute danger. I also think that it would be a good deal, long-term.
Of course one will have to ensure that the migrants indeed leave, and do not come back too soon, or nothing would be gained. One could perhaps pay the premium through the governments of their home country, possibly in the form of real estate or a pension. That would combine an incentive for the home countries with one for their citizens.
This economical calculus would only work if the home countries stayed stable for an extended period of time (or the returned migrants would have to migrate again, this time with a good reason). It must be the goal of the European countries to aim at stability in those regions. But that is the goal anyway, I hope; its importance was fairly prominent in recent months.
