Pyth, 26 bytes

LsI@b2 fy=sh.fys+QZ1\0)@Q2 

Test suite

Output is as a float. If output as an int is desired, it would be 1 extra byte.

Explanation:

LsI@b2 fy=sh.fys+QZ1\0)s@Q2 Q = eval(input()) L def y(b): return @b2 Square root of b sI Is an integer. f ) Find the first positive integer T that satisfies h.f 1\0 Find the first digit string Z that satisfies +QZ Concatenation of Q and Z s Converted to an integer y Is a pergect square. s Convert the string to an integer = Assign result to the next variable in the code, Q y Repeat until result is a perfect square (The space) Discard return value @Q2 Take square root of Q and print. 

MATL, 35 44.0 bytes

XK``x@2^tVKVXf1=a~]VKVnQ0h)UXKX^t1\ 

Try it online!

XK % implicit input: n. Copy to clipboard K ` % do...while. Each iteration applies the algorithm ` % do...while. Each iteration tests a candidate number x % delete top of stack @2^ % iteration index squared t % duplicate V % convert to string K % paste from clipboard K: n or r_k V % convert to string Xf % find one string within another. Gives indices of starting matches, if any 1=a~ % test if some of those indices is 1. If not: next iteration ] % end. We finish with a perfect square that begins with digits of n or r_k V % convert to string K % paste from clipboard K: n or r_k VnQ0h % index of rightmost characters, as determined by r_k ) % keep those figures only U % convert to number. This is the new r_k XK % copy to clipboard K, to be used as input to algorithm again, if needed X^ % square root 1\ % fractional part. If not zero: apply algorithm again % implitic do...while loop end % implicit display 

Python 2, 98

i=input();d=o=9 while~-d: n=i;d=o+1;o=i=0 while(n*d+i)**.5%1:i=-~i%d;d+=9*d*0**i print'%d'%n**.5 

Try it online.

Python, 200 198 178 bytes

import math def r(i): j=int(i**.5)+1 while str(j*j)[:len(str(i))]!=str(i):j+=1 return int(str(j*j)[len(str(i)):]) q=r(int(input())) while math.sqrt(q)%1!=0:q=r(q) print(q**.5) 

Brachylog, 26 bytes

{~a₀X√ℕ∧YcX∧Yh?∧Ybcℕ≜!}ⁱ√ℕ 

Try it online!

The last test case was omitted in the TIO link because it alone takes more than a minute to execute. I ran it on my laptop and the correct result was achieved in no more than two hours.

{ The input ~a₀ is a prefix of X√ X, the square root of which ℕ is a whole number. ∧YcX Y concatenated is X. ∧Yh? The input is the first element of Y. ∧Yb The rest of Y, c concatenated, } is the output ℕ which is a whole number. ≜ Make sure that it actually has a value, ! and discard all choice points. { }ⁱ Keep feeding that predicate its own output until √ its output's square root ℕ is a whole number which is the output. 

The second-to-last ℕ is necessary for when the initial input is already a perfect square, so the first perfect square which has it as a prefix is itself, and ! is necessary to make sure that backtracking iterates instead of finding a larger concatenated square, but I don't really know why ≜ is necessary, I just know that 5 produces a wrong answer without it.

Perl 6, 101 bytes

my&q={$^k;$_=({++($||=$k.sqrt.Int)**2}.../^$k/)[*-1];+S/$k//} put (q(get),&q...!(*.sqrt%1))[*-1].sqrt 

my &q = { $^k; # declare placeholder parameter # set default scalar to: $_ = ( # a list # code block that generates every perfect square # larger than the input { ++( $ ||= $k.sqrt.Int )**2 } ... # produce a sequence /^$k/ # ending when it finds one starting with the argument )[*-1]; # last value in sequence # take the last value and remove the argument # and turn it into a number to remove leading zeros +S/$k// } put ( # print the result of: q(get), # find the first candidate &q # find the rest of them ... # produce a sequence !(*.sqrt%1) # ending with a perfect square )[*-1] # last value in sequence .sqrt # find the sqrt 

ES7, 116 bytes

n=>{do{for(i=n;!(r=(''+Math.ceil((i*=10)**0.5)**2)).startsWith(+n););n=r.replace(+n,'');r=n**0.5}while(r%1);return r} 

Yes, I could probably save a byte by using eval.