Maxwell's equations, which describe electromagnetic fields including light beams in full generality as long as you don't ask about photons, are linear. The air in for all practical purposes linear. The laser beams will pass right through each other without noticing.
However, according to quantum theory, electromagnetic fields are described by QED. This entails photons sometimes appearing briefly as electron-positron pairs (and muon-antimuon, etc.) although very rarely for any practical apparatus if your budget is less than several million dollars.
High-power intersecting laser beams is one way to ignite hydrogen fusion at the Nation Ignition Facility at Lawrence Livermore. I suppose they have to worry about interference. Of course, the beams do interact at the fuel pellet,
Search terms to try: "photon-photon scattering", "QED box diagrams"
There is also the fact that all transparent materials exhibit nonlinearities at sufficiently high intensities. For air, it takes quite a lot.
Here's the abstract of a paper on measuring nonlinear optical effect in air at near infrared frequency using a 100GW laser: http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-14-13-6194