Methods for calculating the number of zeros of a polynomial with a specified real part?

I realized that my comment actually answers your question completely for $(x+1)^p-x^p-1$. After raising to the power $p/(p-1)$ the counting criterion simplifies quite a bit: Compute $$ \cos\left(\frac{2 \pi n}{p-1}\right)$$ for $n=0, \ldots, \lfloor(p-1)/4\rfloor$. Every value in $(0, \tfrac12]$ adds four roots and $0$ adds two roots. In other words: every $ (p-1)/6 \leq n < (p-1)/4$ counts for four roots and $n=(p-1)/4$ (if $p\equiv 1 \pmod 4$) counts for two roots.

Here is how I derived this root counting method. To avoid my sign mistakes I make the substitution $x \leftarrow -x$ and investigate the roots of $(1-x)^p + x^p - 1$ for odd $p$ on the critical line $\operatorname{Re}(z) = \tfrac12$. Note that on the critical line $1-z=\overline{z}$ so $z$ is a root if and only if $\operatorname{Re}(z^p) = \tfrac12$. The strategy is now to investigate the image of the critical line under all branches of $z^{1/p}$ and see how often this image intersects the critical line. Let $f_0(z)=z^{1/p}$ indicate the principle branch. The other branches are then $$f_m(z)=\exp\left(\frac{2 \pi \mathrm{i}\,m}p\right)f_0(z)$$ for integral $m$. Here $m$ will be restricted to $[0, (p-1)/4]$, i.e. those $m$ for which the primitive $p$-th root lies in the upper right quadrant. Now parameterise the critical line by $$z = \tfrac12(1 + \mathrm{i}\tan(\alpha))$$ for $\alpha \in (-\pi/2, \pi/2)$. A straight forward computation shows that $$N_m(z) = (\operatorname{Re}f_m(z))^p = \frac{\cos^p((\alpha + 2 \pi m)/p)}{2 \cos(\alpha)}.$$ Another straight forward calculation shows that $N_m$ attains its extremal value at $$\alpha = \frac{2 \pi m}{p-1}$$ with extremal value $$N_m(z) = \tfrac12\cos^{p-1}\left(\frac{2 \pi m}{p-1}\right).$$

Now the central observation is this: The image of the critical line under $f_m$ looks a bit like a hyperbola. See this picture for $p=5$ which shows all branches:

So if at this extremal angle $0 < N_m(z) \leq 2^{-p}$ then $0 < \operatorname{Re}f_m(z) \leq \tfrac12$ and the image of $f_m$ will intersect the critical line in two places (counting multiplicity) since the branch is located at the right of the extremal value. By conjugate symmetry this $m$ accounts for four zeroes on the critical line.

for $m=(p-1)/4$ the situation is a bit different: the image now has the imaginary axis as one of its asymptotes. (As visible in the picture for $p=5$. The extremal value $N_m(z)$ is $0$ in this case.) This branch clearly intersects the critical line only at a single point, accounting for two zeroes on the critical line in total.