Here is the question:
Let $A$ be any regular set over some alphabet $\Sigma$. Is the language $$ L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\} $$ necessarily regular?
I am unable to approach this question to prove whether it is regular or not. In fact, this seems like a difficult question. Unlike with other regular language problems, it does not seem intuitively clear whether or not the statement is true.
To my knowledge, the best answer to this (type of) problem was given in [1]. Here is a sketch of this proof. I will use freely the notation $u^{-1}L = \{v \in A^* \mid uv \in L\}$.
Proof. Let $K$ be a regular language of $A^*$ and let $\mathcal{A} = (Q, A, q_0, F)$ be its minimal DFA. For each state $q \in Q$, consider the regular languages $$ \text{$L_q = \{x \in A^* \mid q_0 x = q\}$ and $R_q = \{y \in A^* \mid q y \in F\}$.} $$ Observe that if $x \in L_q$, then $$ R_q = \{y \in A^* \mid q_0xy \in F\} = \{y \in A^* \mid xy \in K\} = x^{-1}K \qquad (1) $$ We are interested in the language \begin{align} M &= \{ x \in A^* \mid \text{there exists $y \in A^*$ such that $|y| = |x|^2$ and $xy \in K$} \} \\ &= \{ x \in A^* \mid xA^{|x|^2} \cap K \not= \emptyset\} \\ &= \{ x \in A^* \mid A^{|x|^2} \cap x^{-1}K \not= \emptyset\} \end{align} Since $A^* = \bigcup_{q \in Q} L_q$, it suffices to prove that, for each $q \in Q$, $M \cap L_q$ is regular. Now by (1), we get \begin{align} M \cap L_q &= \{ x \in L_q \mid A^{|x|^2} \cap x^{-1}K \not= \emptyset\} \\ &= \{ x \in L_q \mid A^{|x|^2} \cap R_q \not= \emptyset\} \qquad (2) \end{align} At this point, one needs the fact that, for each regular set $R$ of $A^*$, the set $\{|u| \mid u \in R\}$ is an ultimately periodic subset of $\mathbb{N}$. (You can prove this as an exercise, or use the fact that rational subsets of monoids are closed under morphisms, if you know what it means). In particular, the set $N_q = \{|u| \mid u \in R_q\}$ is an ultimately periodic subset of $\mathbb{N}$. Moreover, it follows from (2) that $$ M \cap L_q = \{ x \in L_q \mid |x|^2 \in N_q \} $$ A little effort is still needed to show that if $S$ is an ultimately periodic subset of $\mathbb{N}$, then $\{n \in \mathbb{N} \mid n^2 \in S\}$ is also ultimately periodic. A similar property holds not only for $n^2$, but for many other functions of $n$, as shown in [1]. In particular $M_q = \{n \in \mathbb{N} \mid n^2 \in N_q\}$ is ultimately periodic and we get $$ M \cap L_q = \{ x \in L_q \mid |x| \in M_q \} $$ It follows that $M \cap L_q$ is regular, which concludes the proof.
[1] J. I. Seiferas and R. McNaughton, Regularity-preserving relations, Theoret. Comput. Sci. 2 (1976), no. 2, 147--154.