It's a good question and it isn't obvious that both observers will agree on the magnitude of their relative velocity. It's fairly straightforward to show this using the Lorentz transformations, but let me attempt a more intuitive approach (if you want to see the maths comment to this answer and I can append it).
You have chosen an inertial frame $S_1$ where observer $A$ is stationary and observer $B$ is moving at some velocity $-v_1$ (we'll take velocities to the right to be positive and to the left to be negative):
In $B$'s rest frame $S_2$ things look like this:
And the point you're making is that it isn't intuitively obvious that $v_1 = v_2$ i.e. that both $A$ and $B$ measure the same relative speed.
To see why $v_1 = v_2$ consider that there must be some third observer $C$ who sees both $A$ and $B$ to have equal and opposite velocities i.e. in $C$'s rest frame $S_3$ the situation looks like this:
In $C$'s frame the motion is symmetrical so the velocities of $A$ and $B$ are equal and opposite. The symmetry is the key point here. There's nothing special about being to the left of observer $C$ or to the right of observer $C$ so we can exchange $A$ and $B$ without changing anything - the velocity of the observer to the left remains $v_3$ and the velocity of the observer to the right remains $-v_3$. That means both $A$ and $B$ must observe their opposite number to have the same velocity (though in opposite directions). If $A$ or $B$ measured their opposite numbers to have different speeds it would break the symmetry.
As requested, here's the maths
We'll start in frame $S_1$ i.e. the frame in which observer $A$ is at rest. In this frame $A$ observes $B$ to be travelling at a velocity $v_A$. Our task is to work out what speed $B$ observes $A$ to be moving, and show that this is also $v_A$ (in the opposite direction) thereby proving that both $A$ and $B$ agree on each others relative speed.
To find out where spacetime points in frame $S_1$ map to in $B$'s frame $S_2$ we need to use the Lorentz transformations:
$$\begin{align}
t' &= \gamma \left( t - \frac{vx}{c^2} \right ) \\
x' &= \gamma \left( x - vt \right)
\end{align}$$
We can choose our coordinates so that $A$ and $B$ meet at the origin at time zero i.e. $(t=0, x=0)$ it the same point in each frame.
We do the calculation by choosing the two points in $A$'s frame $(t=0, x=0)$ and $(t=\tau, x=0)$. That is $A$ starts at time zero at $x=0$ and a time $\tau$ seconds later $A$ is still at $x=0$, because after all we are working in $A$'s rest frame. If we can find out where these two points are in $B$'s frame then we can work out how far $B$ observes $A$ to move and in what time, and the speed observed by $B$ is then just the distance divided by the time.
This sounds hard but it's actually a very easy calculation. We already know the starting point $(0,0)$ is the same in both frames, so we just need to work out where the point $(\tau,0)$ is in $B$'s frame. If we take the Lorentz transformations and plug in $t=\tau$ and $x=0$ we get:
$$\begin{align}
t' &= \gamma \left( \tau - \frac{v_A\,0}{c^2} \right ) = \gamma \tau \\
x' &= \gamma \left( 0 - v_A\tau \right) = -\gamma\tau v_A
\end{align}$$
So in $B$'s rest frame $A$ starts at $(0,0)$ and moves to $(\gamma\tau, \gamma\tau v_A)$ i.e. $A$ has moved a distance $\gamma\tau\ v_A$ in a time $\gamma\tau$. The velocity observed by $B$ is just distance moved divided by time, so:
$$ v_B = \frac{-\gamma\tau v_A}{\gamma\tau} = -v_A $$
And there's your answer. If $A$ observes $B$ to be moving at $v_A$ then $B$ observes $A$ to be moving at $-v_A$.
