General Relationship Between Standard Error and Sample Size Suppose I empirically estimate the standard error of some statistic to be 10% (perhaps I do this by bootstrapping). 
Now, I want to know how much I need to increase the sample size to reduce the error to 5%. The estimate and sample are arrived at through complex procedures, and theoretically determining the relationship between sample size and standard error is not feasible. However, I believe that the standard error decreases as sample sizes increases.
Is it plausible to assume that standard error is proportional to the inverse of the square root of n (based on the standard error of a sample mean using simple random sampling)? 
se = s / sqrt( n )
Do standard errors behave (very) roughly in this way in general in relation to  sample size, regardless of the estimate and the sampling procedure? How bad of an assumption is this? 
 A: 
regardless of the estimate and the sampling procedure?

No, you will not have a "root-n" effect regardless of those things, since at least some standard errors do not scale with $\sqrt{n}$.
Many do -- quite possibly all the ones you will be likely to use -- but that's not all of them.
For things that do scale with $\sqrt{n}$ then you expect to halve the standard error by quadrupling sample size. So (at least if we're ignoring sampling variation in the estimate of $\sigma$), that's probably what you need.
One example of something that isn't proportional to $\frac{1}{\sqrt{n}}$ is the standard error of a kernel density estimate when the bandwidth is itself chosen as a function of $n$. [For some common choices of bandwidth formula the standard error goes down as $n^{-2/5}$ instead.]
A: Yes, generally, more samples would lead to smaller standard error. However, since adding more data is generally a random process, the decrease in standard error is not monotonic. 
Consider the special case of Monte Carlo. Suppose you draw i.i.d samples from a distribution $F$, $X_1, X_2, \dots, X_n$. Suppose $Var_F(X_1) = \sigma^2$ and the mean is $E_F(X_1) = \mu$. Consider the task of estimating $\mu$ with the sample mean. Then,
$$ \hat{\mu} = \dfrac{1}{n} \sum_{i=1}^{n} X_i.$$
The variance of $\hat{\mu}$ can be estimated having obtained the sample variance,
$$\hat{\sigma}^2 = \dfrac{1}{n-1} \sum_{i=1}^{n}(X_i - \hat{\mu})^2. $$
Note that $\hat{\sigma}^2 \overset{a.s.}{\to} \sigma^2$ as $n\to \infty$. Due to this convergence, with more samples, we keep bettering our estimate of $\sigma^2$, and the general trend is a decrease in the standard error $\hat{\sigma}/\sqrt{n}$.
However, if we add a new observation $X_{n+1}$ that lies in the tails of $F$, it is possible for that the new estimate of the variance $\sigma^2$ is larger than the old estimate, so that $\hat{\sigma}/\sqrt{n+1}$ is larger that the previous standard error.
If I understand the rest of your question correctly, you want the standard error to reduce from 10 units to 5 units. Suppose you have $n_1$ samples that gave you a standard error of 10 units. At the cost of being very approximate, lets equate 10 to the standard deviation of the estimate.
$$10 = \dfrac{\sigma}{\sqrt{n_1}} $$
You want to find $n_2$ so that
$$5 = \dfrac{\sigma}{\sqrt{n_2}} $$
Dividing the two equations,
\begin{align*}
2 & = \sqrt{\dfrac{n_2}{n_1}}\\
\end{align*}
and now you can solve for $n_2$ since you know $n_1$. Of course, this will be an approximate sample size calculation since we used the truth, $\sigma$.
