First, you need to reflect what, in fact, is a CFT. The abstract answer is that
It's a set of correlation functions $\langle O_i(x) O_j(y) \cdots O_k(z) \rangle$ which satisfy certain axioms, like the conformal covariance or the short distance behavior when $x\to y$.
These multi-point functions can be encoded in the generating function, so the same set of axioms can be phrased as
It's a functional $\Gamma[\phi_i]= \langle \exp\int \sum_i O_i(x)\phi_i(x) d\,^nx\rangle$ which satisfies certain set of properties.
Now, consider a gravity theory in an asymptotically AdS spacetime, and consider its partition function given the boundary values of $\phi_i$. It gives a functional
$Z_s(\phi_i|_{\partial(AdS)}=\phi_i)$
This functional automatically satisfies the properties which a CFT generating function satisfies. Conformal covariance comes from the isometry of the AdS, for example. Therefore, abstractly, it is a CFT. (A duck is what quacks like a duck, as a saying goes.)
Now this line of argument does not say why Type IIB on AdS$_5\times$ S$^5$ gives $\mathcal{N}=4$ SYM. For that you need string theory. But everything above this paragraph is just about axiomatics.
So, when there is a consistent theory of gravity on AdS$_{d+1}$ other than string/M-theory, you still get CFT$_d$.
This post has been migrated from (A51.SE)