One obvious parallel between Parshat Devarim and its haftarah is the presence of the word "Eichah", which in both places we read in, um, the Eichah-tune.
This parallel is intimately related to a deeper parallel: the role of judges. In Devarim, Moshe's complaint about being unable to manage the people's quarrels leads him to appoint judges to do it for him. In the haftarah, we read about moral deterioration: "How ["Eichah"] the faithful city has become a harlot! She that was full of justice, righteousness lodged in her, but now murderers..." (Yeshayahu 1:21) And the stated reparation for the sin involves fixing the justice system: "I will restore your judges as before, and your advisors as at the beginning; afterward you will be called 'The city of righteousness, the faithful city'. Zion will be redeemed through justice, and its returnees through righteousness." (1:26-27)
We learn in Bamidbar 35:32-34 that unpunished murder "defiles" the land and cannot be atoned for except by punishment. The language is similar to Vayikra 18:27, which says that sexual immorality also "defiles" the land and leads to exile. In Devarim 4:25-27 we read that idol worship causes exile. These are the clear sources in the Torah for Chazal's statement that idolatry, murder, and sexual immorality lead to destruction. Yeshayahu, by calling for a reformed or more effective justice system, tried to address the second of these three potential causes. Moshe had similar motivations in appointing judges, even if murder and other injustice had not yet become prevalent.
In later generations, the impulse towards idolatry disappeared, but sexual immorality and the absence of justice persisted. The gemara (Gittin 55b-58a) tells a series of stories relating why the second Temple was destroyed. The first is that of Kamtza and Bar Kamtza, and the last is that of "two wicks in one lamp" - that is to say, adultery.
In the Kamtza/Bar Kamtza story, virtually everyone is to blame, but perhaps the ultimate cause of destruction is the rabbis' failure to protest Bar Kamtza's embarrassment. Elsewhere, the gemara (Bava Metzia 58b) likens acute embarrassment to murder. Even if we do not take that statement literally, it remains true that the rabbis, in their role as authorities and arbiters, neglected to justly resolve the dispute between Bar Kamtza and the host, with disastrous consequences.
Thus, the gemara begins with a story about the abdication of justice, and ends with a story of sexual immorality. These were only two causes of the destruction, among others, and can perhaps be subsumed under the general label of "sinat hinam". But they were the most prominent and perhaps most important causes, and thus merit being at the very beginning and end. Perhaps due to this importance, in this week's haftarah we are warned about the presence of murder and the absence of justice.
As far as warnings about sexual immorality, do not feel cheated that there are none in parshat Devarim or its haftarah, or on Tisha Beav. These warnings will come soon enough - two months from now, on the afternoon of Yom Kippur.