It can be done on $O(|E|\log |E|)$, nevertheless implementing it might be cumbersome. I won't get into details of how implement, but a general overview so we can analyze its running time:
For this we will need and adjacency list instead of an adjacency matrix.
Step 1.-, for each vertex split away the vertices, you can split away all the edges for each vertex, it can be done in $O(|E|)$ in total, by traversing each of the adjacency list of each vertex. Then do a DFS to find and store each cycle components in a doubly linked circular list. And we will need an array A of lists, such that list A[i] will have a pointer to each component such that vertex $i$ appears in that component. This can be done while doing DFS.
Step 2 and 3. For each of the lists at each vertex, we will take two adjacent components, and we will ask if both are the same, if they are, remove the first pointer, and continue. If both are different components, join the two lists, for this, in the list we should have a pointer to the position in the doubly linked list of such vertex. Then we can merge two components in $O(1)$. Then remove one of the entries and proceed until we have only one list, and remove it. Repeat for each vertex until only one list remains, such doubly linked circular list will be our eulerian cycle.
The tricky part, and where the $O(\log |E|)$ comes from is on finding if two components are the same. For this we can do relabeling the smallest component, and we will get an amortized time of $O(\log |E|)$, (see Cormen et al's chapter on Kruskal algorithm). Or maybe use a union-find data structure, in such case you can make it amortized $O(|E|\alpha(|E|))$, which is a little better time. It could be possible to get O(|E|) time but a clever use of pointers might be implied and escapes from my intuition currently.
Note that this operation to determine if two components are the same would be in function of $|E|$ instead of $n$, since we are duplicating vertices, but the number of vertices and its duplicates is bounded by $|E|$.
Notice that you are using a graph theory book and for the pure graph theory point of view the complexity is usually irrelevant, and even more irrelevant the implementation details, from that point of view is enough to show that it can be done systematically, and the focus is on how simple you can explain and prove that it is correct, it is very uncommon to find data structures mentioned in such a book, since that is usually out the book's scope.