IIRC, Robber Crabs, the ones that clamber up coconut palms, are half-way to book-lungs from gills. Give their kin ample time, space, some mutations and more oxygen, plus a whiff of artistic license...
Of course, if you've already gene-eered lots of big bugs, like hypothetically breeding dogs from natural toy-poodle size into wolves and ponies or, um, eohippus unto 'shire', then you're half way there...
Can you make your exchange 'tac-nuke plus bio-war' rather than a full-out MAD exchange ?? That leaves you with hot-spots, but not a 'global Chernobyl' and nuclear winter situation. IIRC, MAD would have a very, very long toxic tail...