In general, there is no good way to find the conjugate of a composition. But you can use the following fact:
Fact. Let $M$ be a linear subspace of $\mathbb R^n$, and let $g:M\to\mathbb R\cup\{+\infty\} $ be a convex function. If $\pi_M$ is the orthogonal projection onto $M$, then
$$
(g\circ \pi_M)^*(y) = \begin{cases} g^*(y),\quad &y\in M \\ +\infty,\quad &y\notin M \end{cases} \tag1
$$
Proof. Let $M^\perp$ be the orthogonal complement of $M$. Every vector $x$ decomposes as $x_M+x_{M^\perp}$ where $x_M\in M$ and $x_{M^\perp}\in {M^\perp}$. Therefore,
$$(g\circ \pi_M)^*(y) =\sup_{x_M, \ x_{M^\perp}} \left(\langle y, x_M\rangle+ \langle y, x_{M^\perp}\rangle - f(x_M) \right) \tag2
$$
Observe that $x_{M^\perp}$ appears only in the term $\langle y, x_{M^\perp}\rangle$. If $y\in M$, then $\langle y, x_{M^\perp}\rangle=0$ for all $x_{M^\perp}$ and therefore (2) becomes the formula for $g^*$. If $y\notin M$, then $\sup_{ x_{M^\perp}} \langle y, x_{M^\perp}\rangle =+\infty$. $\Box$
Combining the above fact with your knowledge of one-dimensional conjugate
$$|cx|^*(y)=\begin{cases} 0 , \quad &|y|\le |c| \\ +\infty , \quad &\text{otherwise} \end{cases} \tag3$$
you can conclude with
$$|\langle a,x\rangle|^*(y)=\begin{cases} 0 , \quad &y=ta, \ -1\le t\le 1 \\ +\infty , \quad &\text{otherwise} \end{cases} \tag4$$
The function inside the supremum is homogeneous with respect to $x$: that is, for any $t\ge 0$
$$z\cdot (tx)-f(tx ) = t(z\cdot x -f(x) )$$
If there is $x$ for which $z\cdot x -f(x)>0$, the supremum is infinite (you can multiply that $x$ by arbitrarily large $t$). Otherwise, it is zero (take $t=0$).
If there is some $x$ for which $z\cdot x -f(x)>0$, then there is such $x$ of unit norm (by rescaling). So, the question boils down to maximizing $z\cdot x $ over unit norm vectors $x$. (Of course, this is what the dual norm is.)
For example, look at $l_1$ norm. How to maximize $\sum z_i x_i$ subject to $\sum |x_i| =1$? Pick an index $j$ for which $|z_j|$ is maximal, then set $x_j=\mathrm{sign}\,z_j$ and $x_i=0$ for $i\ne j$. This gives $\sum z_i x_i = |z_j|$. Then argue that one can't get more than that. If you know Hölder's inequality, use it to shorten the proof.
Best Answer
Since the function is radially symmetric, so is its conjugate. So you can as well consider the one-dimensional problem, with $f(x)=|x|+x^2/2$. Recall that the gradient of conjugate function is the inverse of the gradient of $f$.
Again by symmetry, it suffices to consider $x>0$ only. Since $f'(x)=1+x$, the inverse is defined only for $x\ge 1$. Imagine that the discontinuity of $f'$ at the origin "stretches" the origin into $[-1,1]$, which the gradient of the conjugate $f^*$ will collapse back into a point. So, $(f^*)'(v)=(v-1)^+$ which integrates to
$$f^*(v) = \frac12((\|v\|-1)^+)^2 $$ As usual, $a^+=\max(a,0)$.