What do I do? For the most part, you can always adjust your play to accommodate for what the enemy buys, but I'm stumped on this one. As long as he is near me, I lose so much effectiveness in team fights. What item do I build to counter this? How do I play around this item/interaction?
Crit and Damage are always counters to AS reductions. Last Whisper counters bonus armor. 
counters HP and Armor.
Frozen Heart is supposed to counter ADCs who itemize AS. Just like Thornmail counters ADCs who don't build lifesteal.
That's how it's always been.
All you could do is not put yourself in a position to be easily ulti'd by malph. You are going to be ineffective with a malph close to you thanks to his E and the frozen heart, so you need good positioning and hopefully some peel from your teammates.
The attack speed slows are multiplicative, so the more you itemize into attack speed, the more those slows will hurt.
Be sure to build last whisper and probably build a little bit of durability so you can survive the initial malph ult and buy your team time to peel.
In all honesty, more attack speed and crit chance is the best idea. Blade of the Ruined King will help you take health down. Malphite builds lots of armor, so a Dominik's Regards is not the worst option. I personally don't like the new Last Whisper options, but against high armor builds, they help. Some. Sometimes you have to focus the tank to kill everyone else. (Rammus and Malphite are excellent examples.)
But truthfully, if you've built one good Attack Speed item, building another can help.
1 Don't stand next to him.
2 Be 
3 ???
4 Profit
, any crit item, BORK, Ghostblade with active
Buy him flowers, kindness usually works on a frozen heart
Jhin.
is the correct answer.
Generally speaking, Malphite will stack a lot of armor and minimal MR. Ergo, having your mid/top/jungler (at least one of those should be AP-heavy, or your team comp is fucked) take care of him will generally be better than you doing so as an ADC. Malphite is like THE anti-ADC.
