I begin with the questions of the second paragraph. The partition function of a supersymmetric theory only depends on the supersymmetric vacua and so it is not possible to read the BPS spectrum from the partition function. There is no wall-crossing effect for the partition function in $N=2$ $4d$ theory: it is a holomorphic multivalued function with some complex codimension 1 singularities on the Coulomb branch.
Nevertheless, there is a kind of relation between the partition function of a $N=2$ $4d$ theory and "some BPS states". When the $N=2$ $4d$ gauge theory can be obtained by a gravity decoupling limit from a compactification of type $IIA$ string theory on a non-compact Calabi-Yau 3-fold $X$, the Nekrasov partition function can be expressed in terms of the refined Gopakumar-Vafa invariants of $X$, which count $D2-D0$ bound states or equivalently $M2$ branes wrapping holomorphic 2-cycles in $X$. In terms of $M$-theory compactified on $X$, these invariants count BPS states in the $5d$ supergravity theory. These states are related to instantons in $4d$ via compactification on the $M$-theory circle. There is no wall-crossing effect for Gopakumar-Vafa invariants, which is compatible with the absence of wall-crossing effect for the Nekrasov partition function. A subtle point is that these $5d$ BPS states do not give $BPS$ states in the $4d$ gauge theory. They obviously give BPS states in the $4d$ supergravity theory but to obtain the $4d$ gauge theory, one has to take some limit decoupling gravity. In this limit, most of the $D2-D0$ BPS states become of infinite mass and decouple, except for the obvious ones such that the gauge vector multiplets
The first paragraph of the question is about the relation between two 4d/2d correspondences. Here I have only a partial answer. In the two cases the $4d$ side is a $N=2$ $4d$ gauge theory. In AGT, the $2d$ side is a $2d$ CFT (or a massive deformation), typically non-supersymmetric such as Liouville theory. A way to construct $N=2$ $4d$ gauge theories is to compactify the $N=(2,0)$ $6d$ SCFT living on the world-volume of $M5$ branes, on a Riemann surface $C$. The AGT correspondence should be a relation between the $N=2$ $4d$ gauge theory and a $2d$ CFT living on $C$. The simplest statement of AGT is the relation between the Nekrasov partition function of the $N=2$ $4d$ theory and the chiral conformal blocks of some Liouville like $2d$ CFT on $C$. This statement is mainly about supersymmetric vacua of the gauge theory. It is expected that it is possible to extend the correspondence to correlation functions of chiral operators on the gauge theory side. It seems to me that the question to incoporate the full BPS spectrum of the $N=2$ $4d$ theory in a AGT like relation is an open problem.
In the CNV paper, the beginning point is the BPS spectrum of $N=2$ $4d$ gauge theories. For many such theories, the BPS spectrum has some quiver description: the moduli spaces of BPS states have a purely algebraic description as moduli spaces of representations of a quiver. CNV remark that the same object, a quiver, plays a role in the classification of $N=(2,2)$ $2d$ massive theories of Cecotti-Vafa: given a massive $N=(2,2)$ $2d$ theory, one constructs a quiver by associating a vertex to each supersymmetric vacua and an edge two each $2d$ BPS states connecting two given supersymmetric vacua. So CNV suggest that to every $N=2$ $4$ gauge theory, one should associate a $N=(2,2)$ $2d$ theory. For a $N=2$ $4d$ theory obtained as compactification of type $IIB$ string theory on a non-compact Calabi-Yau 3-fold, the corresponding $N=(2,2)$ $2d$ theory should be a part of the worldsheet theory. They check that when the non-compact Calabi-Yau 3-fold is an hypersurface $W=0$, the $IIB$ worldsheet theory indeed contains the $N=(2,2)$ $2d$ Landau-Ginzburg theory of potential $W$.
So, the $2d$ sides of the AGT and CNV correspondences are very different: for AGT, the $2d$ theory is non-supersymmetric, it should be interpreted as a space-time $2d$ theory in a $IIA-M$ theory realization, whereas for AGT, the $2d$ theory is $N=(2,2)$ supersymmetric and should be interpreted as a worldsheet $2d$ theory in a $IIB$ theory realization. I don't know a general relation between these two kinds of $2d$ theory. If it exists, it is necessarely non-trivial because it needs to exchange a spacetime theory with a worldsheet theory. In special cases, such relation exists and is given by the Heterotic/Type $II$ duality. For example, you can go from $II$ on $K3 \times T^2$ to Heterotic on $T^4 \times T^2$. Roughly, one should be able to convert the $2d$ chiral side of AGT to the non-supersymmetric part of the Heterotic worldsheet theory. So, in special cases, the 2d sides of the AGT and CNV correspondences are just worldsheet theories on Heterotic and Type $II$ strings, and the relation between the two, i.e. the fact they correspond to the same $N=2$ $4d$ theory, should be a consequence of some Heterotic/Type $II$ duality.