I've tried solving the same problem yesterday. I managed to brute-force my way to finding all fair and square (palindromes whose square root is a palindrome) numbers from 1 to $10^{14}$:
1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001,
1234321, 4008004, 100020001, 102030201, 104060401, 121242121,
123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201,
12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001,
1004006004001, 1020304030201, 1022325232201, 1024348434201,
1210024200121, 1212225222121, 1214428244121, 1232346432321,
1234567654321, 4000008000004, 4004009004004
My solution was correct, and the second dataset was solved. But I couldn't find a proper way to calculate all fair and square numbers up to $10^{100}$.
I showed this to my wife this morning, and she noticed an interesting pattern of numbers within my list:
121, 10201, 1002001, 102030201, 10000200001, 1000002000001
484, 40804, 4008004, 400080004, 40000800004, 4000008000004
12321, 1002003002001,
Some fair and square numbers re-appear with space padding. Let's try beyond $10^{14}$. Adding some zeros to $1020302030406040302030201$, whose square root is $1010100010101$ - a palindrome!
Wish I had my wife with me when I solved this yesterday.
I don't have a mathematical explanation for this phenomena, but I guess that for some reason, every fair and square number beyond a certain boundary can be built by adding zeros to a smaller palindrome.
Only a partial answer:
To prove the three digit pattern, I find it easiest to write it in terms of $b$, the lowest base, which has to be even and at least $6$. Then we have
$$(\frac b2+1)b^2+(\frac b2+2)b+(\frac b2+1)\\=
(\frac b2)(b+1)^2+(\frac b2+1)(b+1)+(\frac b2)\\=
(\frac b2-1)(b+2)^2+(\frac b2+3)(b+2)+(\frac b2-1)\\=
\frac{b^3}2+\frac {3b^2}2+\frac {5b}2+1$$
where the first three lines make the palindrome explicit in the three bases. I think finding this pattern is rather easy. If one did a computer search up to $1000$ one would find the first four numbers and the pattern is clear. The algebra to verify it is also not hard. We can prove that this pattern will never extend to a fourth base. If we try base $b-1$ we can divide the number by $(b-1)^2+1$ to find the first and third digit. We find it is $\frac b2+2$ as one might expect. The middle digit wants to be $\frac b2+6$ but the total is too high by $3$. Similarly if we try base $b+3$ we find the first and last digits are $\frac b2-2$, the closest middle digit is $\frac b2+8$, but we are $3$ too high again. These patterns are only established by $b=16$ for base $b-1$ and $b=12$ for $b+3$ but we can easily check the smaller numbers. This does not prove that there are no other examples for four successive bases. I think a similar analysis could be done for the five digit pattern but I haven't done it.
Best Answer
This is not an answer!
The examples below a million are :