In The number of conjugacy classes and the order of the group, a key step in the proof of the congruence saying that $G$ being a $p$-group means that $|G| \equiv c(G) \mod{(p^{2}-1)(p-1)}$ is the construction of a finite group (denoted $P$ in that post) whose relations, as given, are satisfied by \emph{every} word in the generators.
Let $Q$ denote a finite $p$-group which has a presentation of the kind possessed by $P$. More precisely, suppose $Q$ is generated by $x_{1}, \ldots, x_{r}$ and that the relations defining $Q$ are given in infinite families, where each family is of the form $w( e_{1}, \ldots, e_{L} ) = 1$, where $w$ is some word in the free group on $L$ generators and $e_{1}, \ldots, e_{L}$ vary independently over all words in $x_{1}, \ldots, x_{r}$.
The reasoning from before should apply (though I cannot fill in all gaps) to describe $\mathrm{Aut}(Q)$ (and obtain its order):
Since $Q$ is finite, an endomorphism $\phi: Q \to Q$ is injective iff it is surjective. So an endomorphism of $Q$ is an Automorphism iff it is surjective. If $\phi(x_{1}), \ldots, \phi(x_{r})$ do not generate all of $Q$, then the subgroup they generate is contained (since $Q$ is finite) in some maximal subgroup $M$ of $Q$. $M$ contains the Frattini subgroup $\Phi(Q)$, so this endomorphism fails to be surjective when it is converted to an endomorphism of the maximal elementary abelian quotient $Q/ \Phi(Q)$.
Gap 1: I do not immediately see how to prove that $|Q/ \Phi(Q)| = p^{r}$. It is clear that, since $Q$ is generated by an $r$-element set, $|Q/ \Phi(Q)| \leq p^{r}$. The nature of the relation set should imply that $Q$ is trivial if $|Q/ \Phi(Q)| < p^{r}$.
Assuming Gap 1 is fillable, when the words expressing $\phi(x_{1}), \ldots, \phi(x_{r})$ are written in terms of $x_{1}, \ldots, x_{r}$, one can form the matrix whose $(i,j)$ entry is the sum of the exponents, regarded as an element of $\mathbb{Z}/(p)$, to which $x_{i}$ appears in $\phi(x_{j})$.
Gap 2: I do not immediately see how to prove that element of $\mathbb{Z}/(p)$ is well-defined.
Assuming Gap 2 is also fillable, the matrix thus obtained will be invertible iff $\phi$ is surjective, and thus an \mathrm{Aut}omorphism of $Q$. Since all $r \times r$ matrices over $\mathbb{Z}/(p)$ arise this way from endomorphisms of $Q$ (assuming Gap 1 is filled), construction of this matrix yields a surjective homomorphism from $\mathrm{Aut}(Q)$ to $\mathrm{GL}(r,\mathbb{Z}/(p))$. What is the kernel of this homomorphism?
The kernel consists of all preimages of the identity matrix under that abelianization modulo $p$ map. If $|Q| = p^{E}$, assuming Gap 1 is filled, $|\Phi(Q)| = p^{E-r}$. Then any kernel element can be obtained by sending $x_{i}$ to $x_{i}f_{i}$ for all $i$, where $f_{i} \in \Phi(Q)$. This means that the order of the kernel is $p^{r(E-r)}$, and that $|\mathrm{Aut}(Q)| = p^{r(E-r)} \Pi_{k=0}^{r-1} (p^{r}-p^{k})$.
Going back to this question for the quaternion group Q_{8}, $\mathrm{Aut}(Q_{8}) \cong S_{4}$ so $\mathrm{Aut}(Q_{8})$ has $\mathrm{GL}(2, \mathbb{Z}/(2) ) \cong S_{3}$ as a quotient. The kernel of this quotient map consists of the automorphisms of $Q_{8}$ which send each element of $Q_{8} \setminus \Phi(Q_{8})$ to itself, except possibly for sign. Since { $\pm{1}$ } $ = \Phi(Q_{8})$, this sounds exactly like what was covered in the discussion of $\mathrm{Aut}(Q)$ above.
Yet I still have trouble obtaining a presentation of the kind $Q$ satisfies for the quaternion group of order 8:
One may say that, in $Q_{8}$, all elements have order dividing 4: $e^{4} = 1$ for all words $e \in \langle x,y \rangle$.
One may also say that, in $Q_{8}$, all elements square to an element of the center: $e_{1}^{2}e_{2} = e_{2}e_{1}^{2}$ for all words $e_{1}, e_{2} \in \langle x,y \rangle$.
These two statements do not capture $Q_{8}$ completely, since the group with those relations turns out to have order $32$:
$T = \langle x,y| e^{4}=1, e_{1}^{2}e_{2} = e_{2}e_{1}^{2} \rangle$ is nonabelian, since the nonabelian group $Q_{8}$ is one of its quotients.
Now consider the element $x^{2}y^{2}(xy)^{2} \in T$. This element is clearly a product of squares, so it is a product of central elements of order dividing 2. It therefore has order dividing 2 itself.
Yet $T/\langle x^{2}y^{2}(xy)^{2} \rangle$ is abelian, since $x^{2}y^{2}(xy)^{2} = 1$ implies $x^{2}y^{2} = (xy)^{-2})$, which implies (since every element has order dividing 4) $x^{2}y^{2} = (xy)^{2} $, which implies (left-multiplying by $x^{-1}$ and right-multiplying by $y^{-1}$) $xy = yx$.
Therefore $x^{2}y^{2}(xy)^{2}$ is a nontrivial element of $T$, so it has order 2. $T/\langle x^{2}y^{2}(xy)^{2} \rangle$ is, therefore, the largest 2-generated abelian group of exponent 4 (and being abelian subsumes the centrality of squares). So $T/\langle x^{2}y^{2}(xy)^{2} \rangle \cong C_{4} \times C_{4}$ and it is now clear that $|T| = 32$.
The question indicated by the title asks whether more relations can be added, in this symmetric fashion, to $T$ to obtain $Q_{8}$. The natural extension of this question is whether or not there exists a 'nice' criterion for looking at an arbitrary $p$-group and determining whether or not it has a presentation of the kind discussed here. Clearly the discussion of $\mathrm{Aut}(Q)$ gives some preliminary necessary conditions for the existence of such a presentation.
Best Answer
A group given by your presentation for words $w_1,...,w_n$ is called relatively free in the variety of groups given by the identities (laws) $w_1=1,...,w_n=1$. For a characterization of relatively free groups see Hanna Neumann's book "Varieties of groups" . The characterization says that $G=\langle X\rangle$ is relatively free with free generating set $X$ iff every map $\phi\colon X\to H$ into a group $H$ satisfying the same identities as $G$ can be extended to a homomorphism $G\to H$ (the extension is then unique). The variety generated by the quaternion group $Q_8$ (i.e. the smallest variety containing that group) is also described in Hanna Neumann's book. It is defined by three identities $[x^2,y]=1, [[x,y],z]=1, x^4=1$ (the second identity actually follows from the other two and is redundant). Also $Q_8$ is 2-generated, so if it was relatively free, its rank would be 2. But the dihedral group of order 8 generates the same variety (see the book), and all homomorphisms from $Q_8$ into $D_8$ have Abelian images. Thus $Q_8$ is not relatively free.