First thing's first: life is an astounding display of emergent properties. I think Nicolai makes that clear in his answer. That is a primary consideration, for how a lot can be achieved with a little. I'd like to make a more philosophical, wishy-washy response to convince you that the genome really isn't all that central to life. Please pardon the metaphors in advance.
The problem we are faced with is that, as Patrick Bateson once quipped,
We can reconstruct a blueprint from a house, but not a recipe from a cake.
I'd also like to directly and overtly add that blueprints don't build houses.
In similar vain, you are assuming that the genome is responsible for complexity, when in fact it is only a collection of organized legible macromolecules. Sure, the genome is of paramount importance, and inheritance is crucial for evolution to produce novel attributes, but the kitchen of life depends on much more than just one its recipe books. And it is equally important to understand that genomes are more like recipe books rather than blueprints; you can make blueprints from existing buildings but you cannot make recipes from the cake. Life (and its complexity) is a little bit like cake in this regard.
I'd like to make an extreme case: the fact that the entire system of life requires liquid water means that the complexity of the whole biosphere and organisms is very much tangled with the properties of our sun and planet. This is absolutely a requisite and part-and-parcel of Earth life. The genome does not encode for the position or movement of stars but its genes are dependent on this arrangement. This complexity is, for the sake of simplicity, unrightfully overlooked (for practical and sensible reasons). Carl Sagan put it most succinctly:
If you wish to make an apple pie from scratch, you must first invent the universe.