Is the universe non-linear?

To add to John Rennie's excellent answer I would like to note that the linearity of a theory depends of what you are asking of it, especially which observables you are interested in.

One example is the optical response of a 2-level atom (see e.g. https://en.wikipedia.org/wiki/Jaynes–Cummings_model). While being linear in the wavefunctions involved it is non-linear in the field strength of the incoming laser, i.e. would have an amplitude dependent effective refractive index.

(Note: my initial example was complete and utter non-sense. Thanks to Mark Mitchison for pointing that out.)

The obvious example is hydrodynamics.

The interactions in a fluid all originate from the interactions between atoms and molecules that are described by quantum mechnics, and QM is as far as we know linear. However the Navier-Stokes equations are (scarily) non-linear and produce all sorts of weird behaviour.

It's an interesting question whether general relativity is a fundamental theory or whether it's an emergent theory based on some more fundamental interactions. The simple answer is that we don't know as there is no evidence either way. The work on this idea is being led by Erik Verlinde.

First things first, there is no proof that the universe is either. An outstanding question in philosophy is the ontological question of whether the universe is defined by mathematics, or if we created mathematics to understand the universe. Your question only makes sense in the former.

With sufficient feedback, you can create remarkable approximations of non-linear systems with linear systems. Likewise, linearity can be seen in many non-linear systems which operate on a manifold if one looks at small scale.

As for superposition, it only is useful for linear systems, or systems which have reasonable linear approximations. An excellent example appears in electrical engineering with "small signal" models. These are models of how a non-linear system (lots of transistors amplifying currents) can look linear within a small region around a chosen point. Many times that is more than sufficient for what we need.