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×T2 to Heterotic on T4×T2. 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.