We consider the problem of merchant storage participating in the regulation market with state-of-charge (SoC) dependent bids. Because storage can simultaneously provide regulation up and regulation down capacities, the market-clearing engine faces the computation challenge of evaluating storage costs under different regulation scenarios. One approach is to employ a bilevel optimization that minimizes the worst-case storage cost among all potential regulation events. However, subproblems of such a bilevel optimization are nonconvex, resulting in prohibitive computation challenges for the real-time clearing of the regulation market. We show that the complex nonconvex market clearing problem can be convexified by a simple restriction on the SoC-dependent bid, rendering the intractable market clearing computation to standard linear programs. Numerical simulations demonstrate that SoC-dependent bids satisfying the convexification conditions increase the profits of merchant storage owners by 12.32-77.38% compared with SoC-independent bids.