Bizarre density results in sampled statistics
I've seen this same density problem on some of the nonclustered indexes on the largest databases that I have access to. First I'll start with a few observations that I've made about histograms and density calculations:


SQL Server is able to use the primary key on the table to infer something about the density of both columns. This means that the density that includes the PK columns will usually be very accurate.
The density calculation for the first column in the statistics is consistent with the histogram. If the histogram does not model the data well then the density may be off.
To create the histogram the StatMan function makes inferences about the data that is missing. The behavior can change depending on the data type of the column.


For one way to look at the problem, suppose that you sample 100 rows from a 10000 row table and you get 100 distinct values. One guess at what the rest of the data in the table is that there are 10000 unique values. Another guess is that there are 100 distinct values but each of the values are repeated 100 times. The second guess may seem unreasonable to you, which I will agree with. However, how do you balance the two approaches when the sampled data comes back unevenly distributed? There is some set of algorithms developed for this by Microsoft contained in the StatMan function. The algorithms may not work for all data disruptions and all sample levels.

Let's go through a relatively simple example. I'm going to use VARCHAR columns like in your table to see some of the same behavior. However, I'll just add one skewed value to the table. I'm testing against SQL Server 2016 SP1. Start with 100k rows with 100k unique values for the FK column:

DROP TABLE IF EXISTS X_STATS_SMALL;

CREATE TABLE X_STATS_SMALL (
ID VARCHAR(10) NOT NULL, 
FK VARCHAR(10) NOT NULL,
PADDING VARCHAR(900) NOT NULL,
PRIMARY KEY (ID)
);
-- insert 100k rows
INSERT INTO X_STATS_SMALL WITH (TABLOCK)
SELECT N, N, REPLICATE('Z', 900)
FROM dbo.GetNums(100000);

CREATE INDEX IX_X_STATS_SMALL ON X_STATS_SMALL (FK);

-- get sampled stats
UPDATE STATISTICS X_STATS_SMALL IX_X_STATS_SMALL;


Here are some samples from the statistics:

╔═════════════╦════════════════╦═════════╗
║ All density ║ Average Length ║ Columns ║
╠═════════════╬════════════════╬═════════╣
║ 1.00001E-05 ║ 4.888205       ║ FK      ║
║ 1.00001E-05 ║ 9.77641        ║ FK, ID  ║
╚═════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦═════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬═════════╬═════════════════════╬════════════════╣
║ 1005         ║ 0          ║ 1       ║ 0                   ║ 1              ║
║ 10648        ║ 665.0898   ║ 1       ║ 664                 ║ 1.002173       ║
║ 10968        ║ 431.6008   ║ 1       ║ 432                 ║ 1              ║
║ 11182        ║ 290.0924   ║ 1       ║ 290                 ║ 1              ║
║ 1207         ║ 445.7517   ║ 1       ║ 446                 ║ 1              ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 99989        ║ 318.3941   ║ 1       ║ 318                 ║ 1              ║
╚══════════════╩════════════╩═════════╩═════════════════════╩════════════════╝


For evenly distributed data with one unique value per row we get an accurate density, even with a VARCHAR histogram column and a sample size of 14294 rows.

Now let's add a skewed value and update statistics again:

-- add 70k rows with a FK value of '35000'
INSERT INTO X_STATS_SMALL WITH (TABLOCK)
SELECT N + 100000 , '35000',  REPLICATE('Z', 900)
FROM dbo.GetNums(70000);

UPDATE STATISTICS X_STATS_SMALL IX_X_STATS_SMALL;


With a sample size of 17010 rows the density of the first column is smaller than it should be:

╔══════════════╦════════════════╦═════════╗
║ All density  ║ Average Length ║ Columns ║
╠══════════════╬════════════════╬═════════╣
║ 6.811061E-05 ║ 4.935802       ║ FK      ║
║ 5.882353E-06 ║ 10.28007       ║ FK, ID  ║
╚══════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦══════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS  ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬══════════╬═════════════════════╬════════════════╣
║ 10039        ║ 0          ║ 1        ║ 0                   ║ 1              ║
║ 10978        ║ 956.9945   ║ 1        ║ 138                 ║ 6.954391       ║
║ 11472        ║ 621.0283   ║ 1        ║ 89                  ║ 6.941863       ║
║ 1179         ║ 315.6046   ║ 1        ║ 46                  ║ 6.907561       ║
║ 11909        ║ 91.62713   ║ 1        ║ 14                  ║ 6.74198        ║
║ ...          ║ ...        ║ ...      ║ ...                 ║ ...            ║
║ 35000        ║ 376.6893   ║ 69195.05 ║ 54                  ║ 6.918834       ║
║ ...          ║ ...        ║ ...      ║ ...                 ║ ...            ║
║ 99966        ║ 325.7854   ║ 1        ║ 47                  ║ 6.909731       ║
╚══════════════╩════════════╩══════════╩═════════════════════╩════════════════╝


It's surprising that the AVG_RANGE_ROWS is pretty uniform for all steps at around 6.9, even for buckets of keys for which the sample couldn't have found duplicate values. I don't know why this is. The most likely explanation is that the algorithm used to guess at the missing pages does not do well with this data distribution and sample size.

As stated earlier, it is possible to calculate the density for the FK column using the histogram. The sum of the DISTINCT_RANGE_ROWS values for all steps is 14497. There are 179 histogram steps so the density should be about 1 / (179 + 14497) = 0.00006813845 which is pretty close to the reported value.

Testing with a larger table can show how the problem can get worse as the table gets bigger. This time we'll start with 1 M rows:

DROP TABLE IF EXISTS X_STATS_LARGE;

CREATE TABLE X_STATS_LARGE (
ID VARCHAR(10) NOT NULL,
FK VARCHAR(10) NOT NULL,
PADDING VARCHAR(900) NOT NULL,
PRIMARY KEY (ID));

INSERT INTO X_STATS_LARGE WITH (TABLOCK)
SELECT N, N, REPLICATE('Z', 900)
FROM dbo.Getnums(1000000);

CREATE INDEX IX_X_STATS_LARGE ON X_STATS_LARGE (FK);

-- get sampled stats
UPDATE STATISTICS X_STATS_LARGE IX_X_STATS_LARGE;


The statistics object isn't interesting yet. Density for FK is 1.025289E-06 which is close to exact (1.0E-06).

Now let's add a skewed value and update statistics again:

INSERT INTO X_STATS_LARGE WITH (TABLOCK)
SELECT N + 1000000 , '350000',  REPLICATE('Z', 900)
FROM dbo.Getnums(700000);

UPDATE STATISTICS X_STATS_LARGE IX_X_STATS_LARGE;


With a sample size of 45627 rows the density of the first column is worse than before:

╔══════════════╦════════════════╦═════════╗
║ All density  ║ Average Length ║ Columns ║
╠══════════════╬════════════════╬═════════╣
║ 2.60051E-05  ║ 5.93563        ║ FK      ║
║ 5.932542E-07 ║ 12.28485       ║ FK, ID  ║
╚══════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦═════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬═════════╬═════════════════════╬════════════════╣
║ 100023       ║ 0          ║ 1       ║ 0                   ║ 1              ║
║ 107142       ║ 8008.354   ║ 1       ║ 306                 ║ 26.17787       ║
║ 110529       ║ 4361.357   ║ 1       ║ 168                 ║ 26.02392       ║
║ 114558       ║ 3722.193   ║ 1       ║ 143                 ║ 26.01217       ║
║ 116696       ║ 2556.658   ║ 1       ║ 98                  ║ 25.97568       ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 350000       ║ 5000.522   ║ 700435  ║ 192                 ║ 26.03268       ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 999956       ║ 2406.266   ║ 1       ║ 93                  ║ 25.96841       ║
╚══════════════╩════════════╩═════════╩═════════════════════╩════════════════╝


AVG_RANGE_ROWS is up to 26. Interestingly, if I change the sample size to 170100 rows (10X the other table) then the average value for AVG_RANGE_ROWS is again right around 6.9. As your table gets bigger SQL Server will pick a smaller sample size which means that it needs to make guesses about a larger percentage of pages in the table. This can exaggerate statistics problems for certain kinds of data skew.

In conclusion, it's important to remember that SQL Server does not calculate the density like this:

SELECT COUNT(DISTINCT FK) * 1700000. / COUNT(*) -- 1071198.9 distinct values for one run
FROM X_STATS_LARGE TABLESAMPLE (45627 ROWS);


Which for some data distributions will be very accurate. Instead it uses undocumented algorithms. In your question you said that your data wasn't skewed, but the INSTANCEELEMENTID value with the highest number of associated IDs has 12 and the most common number is 1. For the purposes of the algorithms used by Statman that could be skewed.

At that point there's nothing that you can do about it except for gathering stats with a higher sample rate. One common strategy is to gather statistics with FULLSCAN and NORECOMPUTE. You can refresh the stats with a job on whatever interval makes sense for your rate of data change. In my experience a FULLSCAN update isn't as bad as most people think, especially against an index. SQL Server can just scan the entire index instead of the entire table (as it would do for a rowstore table against an unindexed column). Additionally, in SQL Serer 2014 only FULLSCAN stats updates are done in parallel, so a FULLSCAN update can finish faster than some sampled updates.